[11727] 2×n 타일링 2

11726 번 문제에서 2개만 바꾸면 된다

1) 초깃값 fibo[2] = 3

2) 점화식 fibo[i-2]*2

 

점화식을 바꾼 이유는 ㅣ자 바가 하나로 합쳐진게 생겼다고 해서 ㅣ자 바 모양을 가진 fibo[i-2]를 두배했다.

 

import sys

input = sys.stdin.readline

n = int(input())

fibo = [0] * 1002

fibo[0]=0

fibo[1] = 1

fibo[2] = 3

for i in range(3,1002):

    fibo[i] = (fibo[i-1] + fibo[i-2]*2) %10007

print(fibo[n])