카펫

프로그래머스의 '카펫' 문제는 격자의 개수와 넓이 사이의 관계를 이용하는 완전 탐색(Brute Force) 유형입니다. 수학적인 특징을 이해하면 아주 간단하게 풀 수 있습니다.

---

1. 핵심 아이디어: "약수와 둘레의 관계"

카펫의 가로 길이를 w, 세로 길이를 h라고 가정해 봅시다. (문제 조건에 따라 w >= h입니다.)

1. 전체 격자 수: 가로 $\times$ 세로 = brown + yellow
2. 노란색 격자 수: 노란색은 갈색에 둘러싸여 있으므로, 가로와 세로에서 각각 2를 뺀 값의 곱입니다.
   • (w - 2) * (h - 2) = yellow
3. 갈색 격자 수: 전체 격자에서 노란색을 뺀 값입니다.
   • brown = (w * h) - yellow
   • 또는 테두리의 특징을 이용해 brown = 2w + 2h - 4로 계산할 수도 있습니다.

풀이 전략:

• 전체 넓이(brown + yellow)의 약수 쌍을 모두 찾습니다.
• 그 약수 쌍(w, h) 중에서 (w - 2) * (h - 2) == yellow를 만족하는 쌍이 정답입니다.

---

2. 알고리즘 시각화

카펫의 구조를 보면 왜 가로세로에서 2를 빼야 노란색 격자가 나오는지 알 수 있습니다.

---

3. 파이썬 정답 코드 (상세 주석 포함)

Python

 

def solution(brown, yellow):
    # 전체 격자의 개수는 갈색과 노란색의 합
    total = brown + yellow
    
    # 카펫의 세로 길이(h)는 최소 3부터 시작 (노란색이 최소 1칸 있으려면 가로세로가 최소 3이어야 함)
    # 전체 넓이의 제곱근까지만 확인해도 모든 약수 쌍을 찾을 수 있음
    for h in range(3, int(total**0.5) + 1):
        # 전체 넓이가 세로 길이 h로 나누어 떨어지는 경우에만 가로 길이를 구할 수 있음
        if total % h == 0:
            w = total // h # 가로 길이 계산
            
            # 실제 노란색 격자의 개수가 공식 (w-2)*(h-2)와 일치하는지 확인
            # (가로-2) * (세로-2)가 내부의 노란색 영역임
            if (w - 2) * (h - 2) == yellow:
                # 조건에 맞는 [가로, 세로] 반환 (문제에서 가로 >= 세로라고 했으므로 w가 먼저)
                return [w, h]

---

4. 이 문제의 포인트

• 완전 탐색의 범위: 세로 길이 h를 3부터 시작해서 전체 넓이의 제곱근까지만 조사하면 효율적입니다. 어차피 w >= h이므로 그 이상의 h는 조사할 필요가 없기 때문입니다.
• 수학적 모델링: 도형 문제처럼 보이지만, 실제로는 $w \times h = S$와 $(w-2) \times (h-2) = S'$라는 연립방정식을 만족하는 자연수 해를 찾는 과정입니다.