백준 python 11727번 2xn 타일링 2

백준 링크:https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

저번에 풀어봤던 타일링에 경우의 수가 추가된 모습.

n이 늘어날떄마다 나오는 숫자의 패턴을 구해보면 된다.

하나하나 손풀이로 세어보면 [0,1,3,5,11] 이런식으로 나오게 된다.

11을 보면 5 + (3*2)식으로 패턴이 만들어지는 걸 볼 수 있다.

 

풀이 코드:

n=int(input())
dp=[0,1,3,5]
# n=1 [1]
# n=2 [3]
# n=3 [5]
# n=4 [11]
for i in range(4,n+1):
    dp.append(dp[i-1]+dp[i-2]*2)
print(dp[n]%10007)