https://www.acmicpc.net/problem/11726
시간 1초, 메모리 128MB
input :
- n (1 <= n <= 1,000)
output :
- 2 * n 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력.
조건 :
- 1 '*' 2, 2 '*' 1 타일로 채우는 방법의 수.
기저 사례
오른쪽 끝에 1칸을 추가 하려 할 때 가능 한 경우의 수 1개(2 '*' 1)
오른쪽 끝에 2칸을 추가 하려 할 때 가능 한 경우의 수 1개(1 '*' 2 타일 2개 이용)
2 '*' 1 2개를 써도 되지 않냐???
중복의 경우가 발생하기에 독립적인 경우만 생각하자.
점화식
if n == 1 -> 1
if n == 2 -> 2
n = (n - 1) + (n - 2)
import sys
n = int(sys.stdin.readline())
dp = [0, 1, 2]
for i in range(3, 1001):
dp.append(dp[i - 1] + dp[i - 2])
print(dp[n] % 10007)
