[백준/DP] 11727 2×n 타일링2 (Python, 파이썬)

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

 

 

 

이 문제는 이전에 풀었던 11276 2*n 타일링 문제에서 조건이 추가된 문제이다.

 

이전에는 마지막에 두 가지 경우가 올 수 있었으나, 이 문제의 경우에는 세가지 경우가 올 수 있다. 

그러므로 이 문제의 점화식은 

D[n] = D[n-1] +  D[n-2] * 2 

이다.

 

n = int(input())
D = [0 for _ in range(n+1)]

if n == 1: print(n)
elif n==2: print(n+1)
else:
    D[1] = 1
    D[2] = 3

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