11727 - 2 x n 타일링2

 

---

 

문제

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

11727번: 2×n 타일링 2

 

풀이

 

2 x n 타일링 문제와 거의 유사하다. (풀이 링크 : https://whiporithm.tistory.com/6 )

 

차이점이라고는 2 * 2 타일이 하나 더 들어온 것.

따라서  = 타일이 ㅁ 타일이 될 수 있다. 그렇기에 경우의 수를 2배로 설정해주면 답이 나온다.

 

코드

 

n = int(input())

d = [0] * 1001

d[1] = 1
d[2] = 3

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