백준 알고리즘 11727번 2×n 타일링 2(python)

기본적인 다이나믹 프로그래밍 문제이다. 11726번 2×n 타일링과 비슷한 문제이다.

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