[프로그래머스] (Python) - 카펫

문제 분류 : 완전탐색 Lv.2

생각

종이에 몇개 그려보면서 점화식을 세워보았다.

• yellow = (width -2) * (height - 2)
• brown = (width * height) - yellow

이걸 통해서 딱 떨어지는 어떤 식을 도출해 내지는 못했다. 그래서 width와 height에 값을 계속 바꾸어 대입해보면서 위 식에 부합하는지 확인하는 방법으로 코드를 짰다.

이때 범위가 중요하다고 생각하는데, 문제에서 보면 yellow의 최대 범위는 2,000,000이고, brown은 5,000이다.

가장 width가 길어질때는 height이 3칸이면서 동시에 brown의 최댓값일때일 것이다.

대략적으로 계산해보자면, brown은 맨 위, 맨 아래 두줄로 이루어져있다. 그러므로 나누기 2를 해주면 최대 width는 2,500이 나온다.

Code(python)

def validate_check(brown, yellow, height, width):
    if yellow == (width - 2) * (height - 2) and (brown == width * height - yellow) :
        return True
    return False

def get_width_height(brown, yellow):
    for height in range(1, 2500):
        for width in range(height, 2500):
            if (validate_check(brown, yellow, height, width)) :
                return [height, width]



def solution(brown, yellow):
    return get_width_height(brown, yellow)