11726번: 2×n 타일링
문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
풀이
n = int(input())
dp = [0, 1, 2]
dp = dp + [0 for i in range(n-2)]
if n > 2:
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
print(dp[n] % 10007)설명
n이 3이상일때부터 f(n) = f(n-1) + f(n-2)가 성립된다
| n | 방법의 수 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
