[프로그래머스] 카펫 문제 풀이 (Python) : 완전 탐색 알고리즘

문제 설명

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.

Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

 

제한사항

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

 

입출력 예

brown	yellow	return
10	2	[4, 3]
8	1	[3, 3]
24	24	[8, 6]

 

문제 풀이

우선 경우의 수를 모두 구하기 위해 노란색을 기준으로 yellow의 약수를 구했다.

단, 여기서 yello의 약수를 모두 구할 필요는 없으므로 yellow의 제곱근까지만 약수를 탐색했다.

(왜냐하면 16의 약수를 구한다고 가정할 때, 1, 2, 4만 있으면 16과 나누어 나머지 약수를 구할 수 있으므로)

 

이제 구한 약수들로 조건에 맞는 가로, 세로 값을 찾는다.

brown은 yellow를 1줄로 둘러쌓고 있으므로 (yellow의 가로 * 2) + (yellow의 세로 * 2) + 4 가 brown의 값이 된다. 따라서 해당 조건에 맞을 때 yellow의 가로 + 2가 전체 가로, yellow의 세로 + 2가 전체 세로 길이에 해당하므로 두 값을 append하고 무조건 가로 길이가 세로 길이보다 같거나 크므로 내림차순으로 정렬해주면 된다.

import math
def solution(brown, yellow):
    answer = []
    yellow_divisor = [i for i in range(1, int(math.sqrt(yellow))+1) if yellow%i == 0]
    for y in yellow_divisor:
        x = yellow//y
        if brown == (2*x + 2*y + 4):
            answer.append(x+2)
            answer.append(y+2)
            break
    answer.sort(reverse=True)
    return answer