백준 11726 파이썬 2×n 타일링 문제 해설 코드 포함

2025-05-11

18

🧩 백준 11726번: 2×n 타일링 문제 해설

2×n 타일링 문제는 동적 프로그래밍(DP) 패러다임을 활용하여 해결하는 대표적인 알고리즘 문제이다. 이 문제는 간단한 형태의 타일 채우기 문제이지만, 점화식을 도출하는 과정과 효율적인 구현 방법을 배울 수 있는 중요한 기초 문제이다.

1. 📝 문제 분석과 이해

1.1. 문제 설명

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 문제이다2.
입력으로 n이 주어질 때(1 ≤ n ≤ 1,000), 채우는 방법의 수를 _10,007로 나눈 나머지_를 출력해야 한다2.

1.2. 문제 예시 이해

n=1일 때: 세로로 타일 1개를 놓는 방법 1가지만 가능하다3 4.
n=2일 때: 세로 타일 2개 또는 가로 타일 2개를 놓는 방법 총 2가지가 가능하다3 4.
n=3일 때: 총 3가지 방법(세로 타일 3개, 세로 타일 1개+가로 타일 1개, 가로 타일 1개+세로 타일 1개)이 가능하다3 4.

1.3. 핵심 관찰사항

타일을 채우는 과정에서 엇갈려 놓기는 불가능하다10.
2×n 직사각형을 채우는 방법은 마지막에 세로 타일 하나를 놓는 경우와 마지막에 가로 타일 두 개를 놓는 경우로 나눌 수 있다10 17.

2. 🧮 동적 프로그래밍 접근 방식

2.1. 상태 정의

dp[n] = 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수15.

2.2. 점화식 도출

마지막에 세로 타일 하나를 놓는 경우: 앞부분은 2×(n-1) 크기의 직사각형을 채우는 방법의 수인 dp[n-1]와 같다10.
마지막에 가로 타일 두 개를 놓는 경우: 앞부분은 2×(n-2) 크기의 직사각형을 채우는 방법의 수인 dp[n-2]와 같다10.
따라서 **dp[n] = dp[n-1] + dp[n-2]**가 된다3 4 10.

2.3. 초기 조건

dp1 = 1: 2×1 크기의 직사각형은 세로 타일 하나로만 채울 수 있다3 4.
dp2 = 2: 2×2 크기의 직사각형은 세로 타일 두 개 또는 가로 타일 두 개로 채울 수 있다3 4.

3. 📈 규칙 패턴 분석

3.1. 피보나치 수열과의 관계

점화식 **dp[n] = dp[n-1] + dp[n-2]**은 피보나치 수열의 점화식과 동일한 형태를 갖는다4 14.
따라서 dp 배열의 값은 초기값만 다르고 성장 패턴은 피보나치 수열과 같이 진행된다14.

flowchart LR
  A[dp[1]=1] --> B[dp[2]=2]
  B --> C[dp[3]=3]
  C --> D[dp[4]=5]
  D --> E[dp[5]=8]
  E --> F[dp[6]=13]
  F --> G[dp[7]=21]
  G --> H[dp[8]=34]
  H --> I[dp[9]=55]

3.2. 각 n값에 따른 결과값

n=1: 1가지 방법3 14
n=2: 2가지 방법3 14
n=3: 3가지 방법3 14
n=4: 5가지 방법10 14
n=5: 8가지 방법10 14
n=6: 13가지 방법4 14
n=7: 21가지 방법14
n=8: 34가지 방법14
n=9: 55가지 방법14

4. 💻 알고리즘 구현 방법

4.1. 바텀업(Bottom-Up) 접근법

작은 문제부터 해결하여 큰 문제를 해결하는 방식이다5.
반복문을 사용하여 dp3부터 dp[n]까지 순차적으로 계산한다5.

def solution(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + dp[i-2]) % 10007
        
    return dp[n]

4.2. 탑다운(Top-Down) 접근법

큰 문제를 작은 문제로 분할하여 해결하는 방식이다5 15.
재귀 함수와 메모이제이션(Memoization)을 활용한다5 15.

def solution(n):
    memo = [-1] * (n + 1)
    memo[1] = 1
    memo[2] = 2
    
    def dp(n):
        if memo[n] != -1:
            return memo[n]
        
        memo[n] = (dp(n-1) + dp(n-2)) % 10007
        return memo[n]
    
    return dp(n)

4.3. 파이썬 구현 예시

문제에서 n은 최대 1,000까지 가능하므로 충분한 크기의 dp 배열을 선언한다3 14.
계산 과정에서 10,007로 나눈 나머지를 저장하여 오버플로우를 방지한다17.

import sys
input = sys.stdin.readline

def tile_2xn():
    n = int(input())
    MOD = 10007
    dp = [0] * 1001
    
    dp[1] = 1
    dp[2] = 2
    
    for i in range(3, n + 1):
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
    
    return dp[n]

print(tile_2xn())

5. 🔍 시간 복잡도와 공간 복잡도 분석

5.1. 시간 복잡도

바텀업 방식: O(n) – 단순한 반복문으로 n번의 계산이 필요하다5.
탑다운 방식: O(n) – 각 상태는 한 번만 계산되며, 메모이제이션으로 중복 계산을 방지한다5 15.

5.2. 공간 복잡도

두 방식 모두 O(n) – n+1 크기의 배열이 필요하다5.
문제에서 n의 최댓값은 1,000이므로 메모리 사용량은 충분히 적다3.

6. 🧠 문제 해결을 위한 심화 해석

6.1. 수학적 증명 접근

이 문제는 조합론적으로도 접근할 수 있다4.
n이 짝수(2m)일 때와 홀수(2m+1)일 때로 나누어 이항계수의 합으로 표현할 수 있다4.
결과적으로 이항계수의 합이 피보나치 수열과 동일한 형태를 보인다4.

6.2. 모듈러 연산 주의사항

큰 n값에 대해 결과값이 매우 커질 수 있으므로, 모든 연산에서 나머지 연산을 수행해야 한다17.
마지막에만 나머지 연산을 수행하면 정수 오버플로우가 발생할 수 있다17.

7. 📚 유사 문제 및 응용

7.1. 관련 문제들

2×n 타일링 2(백준 11727번): 1×2, 2×1, 2×2 타일로 채우는 방법의 수를 구하는 문제17.
프로그래머스 2×n 타일링: 동일한 문제로 다른 사이트에서도 출제된다3 18.

7.2. 응용 가능 분야

DP의 기초적인 패턴을 학습하는 데 적합한 문제이다5.
타일링 문제는 다양한 변형이 있으며, 조합론과 관련된 여러 알고리즘 문제의 기초가 된다4 10.

8. 🔑 핵심 포인트 정리

8.1. 문제 해결의 핵심

직사각형을 채우는 방법을 마지막에 놓는 타일의 형태에 따라 경우를 나누는 것이 중요하다10.
중복된 경우를 세지 않도록 주의해야 한다10.

8.2. DP 문제 접근 방법

작은 사례(n=1, n=2, n=3)부터 직접 그려보며 규칙성을 찾는 것이 효과적이다3 10.
점화식을 도출하고 나면 구현은 비교적 간단하다14.

text1 : dp[1]=1 (세로 타일 1개)
2 : dp[2]=2 (세로 타일 2개 또는 가로 타일 2개)
3 : dp[3]=3 (dp[2]에 세로 타일 1개 추가 + dp[1]에 가로 타일 2개 추가)
4 : dp[4]=5 (dp[3]에 세로 타일 1개 추가 + dp[2]에 가로 타일 2개 추가)
5 : dp[5]=8 (dp[4]에 세로 타일 1개 추가 + dp[3]에 가로 타일 2개 추가)

8.3. 코드 작성 시 주의사항

**나머지 연산(mod 10007)**은 중간 계산 과정마다 적용해야 한다17.
n의 범위가 1부터 1,000까지이므로 배열 크기를 충분히 할당해야 한다3 14.

9. 🎯 종합 요약

본 문제는 동적 프로그래밍의 기초적인 개념을 이해하고 적용하는 좋은 예제이다. 직사각형을 타일로 채우는 방법의 수를 구하는 과정에서 **점화식 dp[n] = dp[n-1] + dp[n-2]**를 도출하였고, 이는 피보나치 수열과 동일한 형태를 가진다.

초기값 dp1 = 1, dp2 = 2에서 시작하여 n까지 순차적으로 계산하는 바텀업 방식이 가장 효율적이며, 계산 과정에서 정수 오버플로우를 방지하기 위해 10,007로 나눈 나머지를 지속적으로 저장해야 한다.

이 문제는 타일링 문제의 기초가 되며, 다양한 변형 문제로 확장될 수 있어 알고리즘 학습에 있어 중요한 기반이 된다.