프로그래머스 - 카펫 (완전 탐색) / Level 2

문제 설명

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]

 

 

풀이

def solution(brown, yellow):
    answer = []
    sum_val = brown//2 + 2  # 가로 + 세로
    multi_val = brown + yellow  # 가로 * 세로
    
    for height in range(sum_val):
        for width in range(height, sum_val):
            if width*height == multi_val and width + height == sum_val:  # 조건에 맞는지 check.
                answer.append(width)
                answer.append(height)
    return answer

연립방정식을 통해서 "가로+세로", "가로*세로" 값을 얻었고 각각의 값은 자연수이기 때문에 

각각의 미지수에 값을 대입하여 찾듯이 순회하기로 하였다.

 

가로, 세로 각각의 값들은 그 값들의 합을 넘지 않을 것이기 때문에 최댓값을 합으로 잡고 순회하였으며

가로의 길이가 세로의 길이보다 길다는 조건을 사용하여

가로길이를 찾는 for문에서 최솟값을 세로 길이로 잡아서 시간 복잡도를 줄여 주었다.

 

 

이 문제가 왜 완전 탐색 카테고리에 속해 있을까?

이 문제를 수학적으로 풀면 두 개의 식이 나오는데

미지수 값들이 자연수라는 조건이 있기 때문에

특정 범위를 정하여 자연수들을 탐색하여 식을 만족하는지 체크해줘야 했다.

 

물론 이 두 개의 식을 통해 이차방정식을 만들어 근의 공식을 활용하여 푸는 방식도 존재하였다.