[백준 11727] 2×n 타일링 2.py

핵심

• n(n>2)번째 직사각형은 (n-1)번째 직사각형에 2X1 타일 하나만 더할 수 있고, (n-2)번째 직사각형에서 2X2 타일 하나, 1X2 타일 두 개를 더 할 수 있다.

  점화식은 f(n) = f(n-1) + f(n-2)*2 이다.

소스코드

n = int(input())
dp = [0]*(n+1)

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

print(dp[n] % 10007)