프로그래머스 - 카펫 [python]

난이도 : level 2
유형 : 완전탐색
출처 : https://school.programmers.co.kr/learn/courses/30/lessons/42842

---

문제 접근

테두리 바로 안쪽 한줄만 갈색 이고,
나머지 안쪽 싹다 노란색을 가지는 카펫에
brown, yellow 수를 받아 [가로,세로] 를 return 하는 문제이다.

어떻게 풀 수 있을까

우선 제한사항에서 가로 길이 >= 세로길이라고 했다.
그리고 brown의 값으로는 무조건 사각형이 될 수 있는 수를 줄테니
brown의 값으로 직사각형의 가로세로를 구할 수 있을 것 같다.

BBBBB
BYYYB
BBBBB

이 경우 brown 12이고,yellow 는 3이다.
return 값은 [5,3]이 되어야 할 것이다.

하나만 더 봐보자

BBBBBB
BYYYYB
BYYYYB
BYYYYB
BBBBBB

이 경우 brown 은 18이고, Y는 12이다.
return 은 [6,5] 이다.

..
음 brown의 개수로 가로 세로를 찾는 방법은 잘못 된 것 같다.

찾아보니 방법은 yellow에 있었다.

핵심 아이디어

전체 격자 수 S = brown + yellow = w × h
노란색은 테두리 제외 내부: yellow = (w - 2) × (h - 2)
조건: w ≥ h, w, h ≥ 3
S의 약수쌍 (w,h) 중에서 (w - 2) × (h - 2) == yellow이면 답이다.

해답 및 풀이

def solution(brown, yellow):
    S = brown + yellow
    
    for h in range(3, int(S**0.5) + 1):
        if S % h == 0:
            w = S // h
            if w >= h and (w - 2) * (h - 2) == yellow:
                return [w, h]