https://www.acmicpc.net/problem/11727
시간 1초, 메모리 256MB
input :
- n (1 <= n <= 1,000)
output :
- 2 '*' n 크기의 직사각형을 채우는 방법의 수를 10,007,로 나눈 나머지를 출력
조건 :
- 1 '*' 2, 2 '*' 1, 2 '*' 2 타일 3가지 존재.
기저 사례.
제일 오른쪽에서 1칸을 채우려 할 때. 경우의 수 1가지.
제일 오른쪽에서 2칸을 채우려 할 때, 경우의 수 2가지.
점화식.
n = (n - 1) + (n - 2) * 2
11726? 같은 경우엔 n = 2 일 때 2가지 였지만.
이 문제 같은 경우엔 2칸을 채우는 방식이 1가지 늘어났기 때문에
n = 2 일 때, 3가지가 된다.
import sys
n = int(sys.stdin.readline())
dp = [0, 1, 3]
for i in range(3, n + 1):
dp.append(dp[i - 1] + dp[i - 2] * 2)
print(dp[n] % 10007)
