[프로그래머스] 카펫

프로그래머스 완전탐색  lv 2 문제인 카펫 문제이다.

프로그래머스

 

 

문제 설명

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

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

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

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

---

 

문제 접근

우선 수학적으로 이 문제를 해결할 수 있을 것 같아서 계산을 해보았다. 그래서 아래 식들을 얻을 수 있었다.

1)   brown + yellow = w * h
2)   yellow = (w-2) * (h-2)

1번식과 2번식을 정리하면 아래와 같은 식도 도출할 수 있다.

3)   b = 2*(w+h) - 4

따라서 먼저 brown + yellow에서 얻은 값을 통해 나올 수 있는 가로와 세로의 조합을 구했고 그 조합 중에서 위 식을 만족하는 값을 찾으면 break 하도록 했다.

 

---

내가 작성한 답

def solution(brown, yellow):
    answer = []
    total = brown+yellow
    w = 0
    h = 0
    for i in range(1, total+1):
        if total%i == 0:  # 가로/세로의 조합 구하기
            h = int(total/i)
            if 2*(i+h)-4 == brown: # 3번식을 만족하는지 확인
                w = i
                answer.append(w)
                answer.append(h)
                break

    return sorted(answer,reverse=True)