[프로그래머스 lv2] 카펫 (파이썬)

문제 설명

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

문제 설명

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

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

제한사항

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

입출력 예

입출력 예

 

---

 

 

 

나의 풀이

def solution(brown, yellow):    
    total = brown + yellow
    for i in range(3, int(total**0.5) + 1):
        if not total % i and (i-2) * ((total//i)-2) == yellow:
            return [total//i, i]

아이디어는 다음과 같다.

 

갈색 격자와 노란 격자의 합이 전체 격자의 크기가 될 것이다.

그리고 전체 격자가 직사각형이 되기 위해서는 가로 x 세로 로 나타낼 수 있어야 한다. 즉, 약수를 구하면 된다.

 

문제의 조건 중 노란 격자가 1 이상이기 때문에 전체 격자의 크기는 최소 3x3 이상이어야 한다.

그래서 for문의 range 범위를 3부터 시작했다.

 

어떤 수의 약수는 항상 짝이 존재한다. 짝을 이루는 두 수가 다른 수라면 하나는 크고 하나는 작을 것이다. (당연한 말)

약수의 짝 중 작은 수는 제곱근보다 크지 않을 것이다. 그렇기 때문에 range 의 끝 범위를 total ** 0.5 까지 하면 된다.

 

i로 나누어 떨어지면 약수인 것이고, 2씩 뺀 수를 곱한 것이 yellow의 크기와 같다면 답을 찾은 것이기 때문에 total//i와 i를 return 하면 된다.

(i 보다 total//i를 먼저 하는 이유는 i가 더 작거나 같은 값이고, 문제 조건에서 가로 길이가 세로 길이와 같거나 더 길다고 했기 때문이다)