문제 21 - 카펫 (Python)

프로그래머스

 

테두리의 갈색 격자와 내부의 노란색 격자 수를 바탕으로 전체 카펫의 가로, 세로 길이를 찾는 문제입니다. 격자 구조의 기하학적 특징을 수식으로 도출하여 가능한 경우의 수를 탐색하는 완전 탐색 문제로 분류됩니다.

---

1.  나의 풀이

def solution(brown, yellow):
    # 노란색 격자의 가로와 세로 합 도출
    # 갈색에서 4개의 귀퉁이를 제외한 노란색의 둘레를 2개로 나눠 구함
    yellow_col_plus_row = (brown - 4) // 2

    yellow_row = 0
    while True:
        yellow_row += 1
        yellow_col = yellow_col_plus_row - yellow_row
        
        # 가로와 세로의 곱이 yellow가 되는 지점 확인
        if yellow_row * yellow_col == yellow:
            # 전체 길이는 노란색 길이에 각각 2를 더한 값
            return [yellow_col + 2, yellow_row + 2]

---

2.  오늘 배운 점 및 복기 노트

노란색 격자 중심의 인덱스 제어
전체 카펫 크기를 기준으로 탐색하기보다 내부의 노란색 영역을 기준으로 삼으면 수식이 간결해집니다. \( yellow\_row + yellow\_col = (brown - 4) / 2 \)라는 관계식을 먼저 도출하여 변수를 하나로 줄인 점이 효율적이었습니다.

while 루프의 종료 조건
문제 조건에서 가로가 세로보다 길거나 같다는 점을 이용해 \( yellow\_row \)를 1부터 증가시키며 탐색했습니다. 별도의 종료 조건 없이도 반드시 답이 존재하는 구조이므로 \( True \)를 활용한 루프가 가능했습니다.

---

3.  프로그래머스 코딩 테스트 문제 풀이 전략 교재에서 배울만한 점

전체 넓이의 약수를 활용한 탐색

교재에서는 \( brown + yellow \)를 합친 전체 넓이 \( grid \)를 구한 뒤, 이 값의 약수 쌍을 찾는 방식을 제시합니다. 세로 길이를 \( n \)이라고 할 때 \( 3 \)부터 \( \sqrt{grid} \)까지 확인하며 \( (n-2) \times (m-2) == yellow \)인지를 검증하는 로직은 약수의 성질을 이용해 탐색 범위를 획기적으로 줄일 수 있습니다.

grid = brown + yellow
# 전체 넓이의 제곱근까지만 탐색하여 효율성 확보
for n in range(3, int(grid ** 0.5) + 1):
    if grid % n == 0:
        m = grid // n
        # 가로, 세로에서 각각 테두리 2칸을 제외한 곱이 yellow인지 확인
        if (n - 2) * (m - 2) == yellow:
            return [m, n]

근의 공식을 이용한 수학적 접근
반복문을 사용하지 않고 이차방정식의 근의 공식을 적용하여 즉시 답을 구하는 최적화 방법을 소개합니다. 둘레와 넓이가 주어졌을 때 두 변의 길이를 구하는 것은 이차방정식의 두 근을 구하는 것과 같으므로, \( O(1) \)의 시간 복잡도로 해결할 수 있습니다. 복잡한 로직 구현 전에 수학적 모델링이 가능한지 검토하면 좋습니다.

꼭 규칙을 찾는 것에 매달릴 필요는 없습니다. 어디까지나 시험의 목표는 문제를 푸는 것이기 때문에 일단 풀고 난 다음에 찾아봐도 늦지 않습니다.

def solution(b, y):
    # 이차방정식의 근의 공식을 활용한 정해 도출
    # b = 2w + 2h - 4 => w + h = (b + 4) / 2
    # w * h = b + y
    term = (b + 4) / 2
    discriminant = (term ** 2 - 4 * (b + y)) ** 0.5
    
    w = (term + discriminant) / 2
    h = (term - discriminant) / 2
    return [int(w), int(h)]