[프로그래머스] 카펫 (Lv.2) - (완전탐색)

문제 설명

프로그래머스 Lv.2 - 카펫 문제

중앙에 노란색 타일로 채워진 직사각형이 있고, 그 주위를 갈색 타일로 감싸서 카펫을 만들었다.
주어진 갈색(brown) 타일 수와 노란색(yellow) 타일 수를 기반으로
카펫의 가로, 세로 길이를 구하라.

---

조건 요약

• 전체 타일 수 = brown + yellow
• (가로 - 2) * (세로 - 2) == yellow 를 만족해야 함
• 가로 ≥ 세로 조건

---

처음에 시도한 방식: 소인수분해 + 조합

from itertools import combinations

def multiple_tuple(tuple):

    result = 1

    for i in tuple:

        result *= i

    return result

def solution(brown, yellow):

    block = brown + yellow

    prime_factor = []

    divide = 2

    result = []

    while block != 1: # 소인수 분해

        if block % divide == 0:

            block = block // divide

            prime_factor.append(divide)

        else:

            divide += 1

    for i in range(1, len(prime_factor)+1):    

        for num in combinations(prime_factor, i):

            a = multiple_tuple(num)

            b = (brown+yellow)//a

            if (a-2) * (b-2) == yellow:

                return [max(a,b), min(a,b)]

 

🔍 회고
정답은 맞지만... 너무 돌아갔다...
소인수분해 → 조합 → 곱셈 → 조건 체크까지,
쓸데없이 복잡한 여정을 돌았다는 걸 깨달았다.

✅ 최적 풀이 (정석 완전탐색)

def solution(brown, yellow):

    total = brown + yellow

    for height in range(3, total//3 + 1):

        width = total // height

        if (height-2) * (width-2) == yellow:

            return [width, height]

 

6줄만에 끝난다.... 콤비네이션이고 자시고...

 

 배운 점

• 때로는 너무 어렵게 생각하지 말자
• 수학적 조건을 잘 정리하면, 더 간단한 풀이가 존재할 수 있다
• 하지만! 돌아돌아 간 덕분에 소인수분해, 조합, 조건 탐색 실력도 쌓였다 ..