백준 11726: 2xn 타일링(python)

 

dp문제

2x1 타일은 1 가지 방법

2x2 타일은 2

2x3 타일은 3

2x4 타일은 5

2x5 타일은 8

...

2x9 타일은 55

 

dp[i] = dp[i-1] +dp[i-2]의 점화식이 나온다

 

N = int(input())
dp = [0]*1001

dp[1] = 1
dp[2] = 2
for i in range(3,1001):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N] % 10007)