[Programmers] 카펫 (Python3)

문제

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]|

문제풀이

맨처음에는 좌표를 하나씩 늘려가면서 갈색과 노란색의 모든 경우의 수를 찾다가 같은 값이 나오면 그 좌표를 리턴하는 형식으로 코드를 짰는데 역시나 시간초과가 떴다.

그래서 조금 더 생각을 간단히 해서 굳이 모든 사각형의 크기가 아니라 안쪽의 노란색 사각형의 크기만 생각해보기로 했는데, 노란색 사각형은 결국 3,3인 사각형일 때 1이므로 여기서 가로로 사각형이 커지면 노란색 사각형도 같이 1증가하고 세로로 커지면 같이 세로로 1증가한다. 따라서 yellow에 주어진 넓이를 구성할 수 있는 사각형의 가로와 세로를 모두 구해준 후, 그 가로와 세로가 구성하는 큰 사각형이 brown의 넓이와 일치한다면 그때의 가로와 세로를 리턴해주면 된다.

코드

def solution(brown, yellow):
    i = 1
    while 1:
        if yellow % i == 0:
            if (i+2)*(yellow/i+2)-yellow == brown:
                    return[max(i+2,yellow//i+2),min(i+2,yellow//i+2)]
   
        i+=1

solution(10,2)

[4, 3]