[DP] 백준 #11726 2xn 타일링 - Python

🗂️ 문제

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

 

💡 접근법

n=1일 때 직사각형을 채우는 방법은 1가지다.

n=2일 때 직사각형을 채우는 방법은 2가지다.

n=3일 때 직사각형을 채우는 방법은 3가지다.

n=4일 때 직사각형을 채우는 방법은 5가지다.

n=5일 때 직사각형을 채우는 방법은 8가지다.

 

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

 

😎 내 코드

import sys

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

dp = [0] * 1001
dp[1] = 1
dp[2] = 2

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

print(dp[n]%10007)

 

✅ 정답 확인