[프로그래머스] 카펫 / 완전 탐색(Brute-force Search)

이미지를 클릭하면 문제 사이트로 이동합니다.

 

 

 

 

💭 문제 이해

 

 

갈색 타일의 개수와 노란색 타일의 개수가 입력으로 주어질 때, 전체 카펫의 가로 길이와 세로 길이를 구하는 문제이다.

수식으로 정리해본다면,

 

1. 가로를 테두리를 포함해서 \(x+2\) 로 표현하고, 세로는 테두리를 포함하여 \(y+2\) 로 표현한다.

2. 위 수식을 기준으로 전체 칸 수는 \((x+2)(y+2) = brown + yellow\) 로 표현할 수 있다.

3. 노란 부분은 \(xy = yellow\) 로 표현할 수 있다.

4. 전체 칸 수를 나타내는 수식을 전개하면 \(xy+2x+2y+4=brown+xy\) 가 되고, 이를 정리하면 \(x+y = \frac{brown-4}{2}\) 라는 관계가 성립된다.

 

즉,

\(y = \frac{brown-4}{2}-x\) 관계를 만족하며 x의 변화에 따른 y 값을 구하다가

\(xy = yellow\) 조건이 만족하는 부분을 찾아내면 해답이 된다.

 

 

이 과정을 코드로 구현하면 다음과 같다.

 

 

 

 

구현 언어: Python

 

def solution(brown, yellow):
    answer = []
    x = 0
    y = brown
    while True:
        x += 1
        y = (brown - 4) // 2 - x
        if x * y == yellow:
            answer.append(y+2)
            answer.append(x+2)
            break
    return answer