[BOJ_11727] 2xn 타일링 2

점화식을 찾아봅시다.

그림을 보고 입력받은 수가 n이라 할 때, n-2번째 까지의 경우는 두 가지이고 n-1번째 까지의 경우는 한 가지입니다.

좀 더 자세히 말하면 n-2번째까지 타일이 채워진 경우에서 너비가 2인 블럭으로 채우면 n번째 항까지 채운 경우가 되고

n-1번째 까지 타일이 채워진 경우에서 너비가 1인 블럭으로 채우면 n번째 항까지 채운 경우가 되는 것입니다.

그래서

 

f(n) = 2 * f(n-2) + f(n-1)

 

이렇게 점화식을 구할 수 있습니다.

 

n = int(input())
dp = [0 for _ in range(1001)]

dp[0] = 0
dp[1] = 1
dp[2] = 3

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

print(dp[n] % 10007)

www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2