프로그래머스 - 완전탐색 > 카펫 (Python)

문제

Leo는 카펫을 사러 갔다가

아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다.

 

카펫 그림

 

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만,

전체 카펫의 크기는 기억하지 못했습니다.

 

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때,

카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 갈색 격자의 수 brown은 8 이상 5,000 이하인 자연수입니다.
• 노란색 격자의 수 yellow는 1 이상 2,000,000 이하인 자연수입니다.
• 카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

 

 

입출력

입출력 예

 

분석

우선 개수를 토대로 행, 열을 완전 탐색을 통하여 유추하여 풀이하는 게 의도겠지만

카펫의 모양을 보아하니, 더 쉬운 공식이 존재할 수도 있을 것 같은 문제입니다.

 

풀이 1

1. x, y가 갈색 카펫의 가로와 세로 길이 이므로, 노란 카펫의 가로와 세로 길이는 x-2, y-2라고 할 수 있습니다.
2. 그러면 노란 카펫의 가로와 세로 길이가 a, b라고 가정할 때, a와 b는 노란 카펫의 약수라고 할 수 있습니다.
3. 이로 인하여 노란 카펫 = a * b
4. 갈색 카펫 = 2(a+2+b+2)+4을 검사하면 a와 b를 찾을 수 있습니다.
5. a 는 x-2, b는 y-2이므로 각각 +2를 해주어 출력해주었습니다.

 

PyCharm 캡쳐

소스 CODE 1

def solution(brown, yellow):
    for row in range(1, int(yellow ** 0.5) + 1):
        if yellow % row == 0:
            col = yellow // row
            if 2 * row + 2 * col + 4 == brown:
                return [col + 2, row + 2]

 

풀이 2

1. 근의 공식으로 풀 수도 있습니다.
2. x * y = brown + yellow인걸 명시하면, 그림처럼 상하좌우 하나씩 뺀 것이 노란 카펫입니다.
3. 그러면 이것을 (x - 2) * (y - 2) = yellow라고 나타낼 수 있으므로,
4. 2x^2 - (brown + 4) x + 2 yellow + 2 brown = 0이라는 공식이 나오고, 이를 통하여
5. 아래처럼 근의 공식을 비슷하게 엮어 풀어낼 수 있습니다.

 

PyCharm 캡쳐

소스 CODE 2

def solution(brown, yellow):
    x = (brown + 4 + ((brown + 4) ** 2 - 16 * (brown + yellow)) ** 0.5) / 4
    y = (brown + yellow) // x

    return [max(x, y), min(x, y)]