백준 11727: 2xn 타일링 2(Python)

문제

2xn 직사각형을 1x2, 2x1과 2x2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2x17 직사각형을 채운 한가지 예이다.

 

 

 

입력

 

첫째줄에 n이 주어진다.( 1≤ n ≤ 1,000)

 

출력

 

첫째 줄에 2xn 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

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

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

 

2x1 타일은 1 가지

2x2 타일은 3 가지 

2x3 타일은 5 가지

2x4 타일은 11 가지 

 

dp[i] = dp[i-1] + 2*dp[i-2] 점화식