🔥

문제

2×n 직사각형을 1×2, 2×1과 1×1 타일로 채우는 방법의 수를 구해보자.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 문제의 답을 10,007로 나눈 나머지를 출력한다.

예제 1 입력

1

예제 1 출력

2

예제 2 입력

2

예제 2 출력

7

예제 3 입력

5

예제 3 출력

228

Source

n = int(input())
# 2×i 크기의 직사각형을 1×2, 2×1, 1×1 타일로 채우는 경우의 수
dp1 = [0 for _ in range(n + 2)]
# 2×(i-1) 크기의 직사각형을 타일로 채운 상태에서, 추가로 1×1 타일을 넣어 새로운 모양을 만들 수 있는 경우
dp2 = [0 for _ in range(n + 2)]

dp1[1] = 2
dp1[2] = 7
dp2[1] = 1
dp2[2] = 3

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

print(dp1[n])

참고