🟨🟫

문제 설명

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

Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 갈색으로 색칠된 격자의 개수는 기억했지만, 전체 카펫의 크기는 기억하지 못했습니다.
Leo가 본 카펫에서 갈색 격자의 수 brown, 노란색 격자의 수 yellow가 매개변수로 주어질 때 카펫의 가로, 세로 크기를 순서대로 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 사항

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

입출력 예

WHY

이 문제를 완전탐색으로 풀어도 되는 이유는 최악의 경우 연산량이 2백만이기 때문이다. 나는 평소 최악의 연산량을 2천만으로 잡고 푼다. 왜 그런지는 아래를 보자.

• 편의상 노란블록을 붉은색, 갈색 블록을 초록색으로 대체하였다.
• 먼저 노란블록으로 만들 수 있는 모든 경우의 수를 조합해본다.
• 테스트케이스3을 예로 들겠다.
• 노란블록 24개로 만들 수 있는 조합은

  24x1
  12x2
  8x3
  6x4

이렇게 4 종류이다. (4x6부터는 위의 카펫을 그저 돌린 것에 불과하기 때문에 고려하지 않는다.)

우리는 조합할 수 있는 모든 노란 블록에 대해 갈색 블록의 개수가 input값과 일치하는지를 확인하면 되는 것이다.

갈색 블록의 개수 = 2(m+2)+2n이다.
왜 그런지는 저 그림을 보며 스스로 생각해보시길.

따라서 최악의 경우를 생각해보면 노란 블록의 개수가 2백만일텐데
우리는 1~루트(2백만)까지의 경우의 수를 확인해보며 갈색 블록의 개수를 맞춰볼 것이기에 예상 연산량은 루트(2백만), 대략 1414 번이 된다. 이는 충분히 남는 시간이다.

CODE

def solution(brown, yellow):
    for i in range(1,int(yellow**0.5)+1):
        if yellow%i != 0:
            continue
        n = yellow//i
        if (i+2+n)*2 == brown:
            return [max(n,i)+2,min(n,i)+2]

NxM 행렬에서 N,M은 자연수이므로 그렇게 되지 않을 경우는 예외처리를 해주었다.