[백준, BOJ] 11727 - 2*n 타일링 2

1. Question

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

1.1 Input

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

1.2 Output

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

1.3 Example

입력	출력
2	3
8	171
12	2731

2. Approach

이전 포스트와 같이 간단한 DP문제다.

2 by 2짜리 칸이 하나 더 생겼으므로, n-2번째항의 영향이 2배로 커진다.

3. Submission

4. Code

import sys
rl = sys.stdin.readline

N = int(rl())

pre_val = 1
ans = 3

for _ in range(2, N):
    ans, pre_val = ans + pre_val * 2, ans

if N == 1:
    print(1)
else:
    print(ans % 10007)