[DP] 백준 #11727 2×n 타일링 2 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/11727

 

💡 접근법

N=1일 때, 2x1 직사각형을 채우는 방법의 수는 2x1 크기의 타일 하나로 채우는 방법 1가지이다.

N=2일 때, 2x2 직사각형을 채우는 방법의 수는 2x1 크기의 타일 2개를 이어붙이는 방법, 1x2 크기의 타일 2개를 이어붙이는 방법, 2x2 크기의 타일 하나로 채우는 방법, 총 3가지이다.

 

N=3일 때, 2x3 직사각형을 채우는 방법은 다음과 같다.

1. 2x2 직사각형에 2x1 직사각형을 이어붙인다.
2. 2x1 직사각형에 1x2 크기의 타일 2개를 이어붙이거나, 2x2 크기의 타일 1개를 이어붙인다.
   이때, 2x1 크기의 타일 2개를 이어붙이는 경우의 수는 1번에 포함되기 때문에 카운트하지 않는다.

이를 점화식으로 나타내면, dp[i] = dp[i-1] + dp[i-2]*2 (N≥3)이다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())

dp = [0] * (N+1)
dp[1] = 1

if N >= 2:
    dp[2] = 3

    for i in range(3, N+1):
        dp[i] = dp[i-1] + dp[i-2]*2

print(dp[N]%10007)

 

🧐 배운 점

• N 범위가 1 =≤ N ≤ 10000 이다. 점화식에 의해 dp[1], dp[2]를 초기화하게 되는데, N = 1일 경우에 대한 예외 처리가 필요하다.

 

✅ 정답 확인