[알고리즘/백준] 11727: 2 x n 타일링 2(python)

1 - |
2 - ||, =, ㅁ
3 - |||, |=, =|, ㅁ|, |ㅁ
4 - ||||, ||=, |=|, =||, ==, ㅁㅁ, ㅁ||, ㅁ=, |ㅁ|, ||ㅁ, =ㅁ

이렇게 규칙을 찾으면 된다.
dp[i - 1] + dp[i - 2] * 2

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