📩 출처
문제
2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×17 직사각형을 채운 한가지 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
👉 생각
- 규칙을 찾아보면
i번째의 사각형을 채우는 방법의 수는i-1번째와i-2번째에서 2를 곱한 값을 더해주면 되는 것을 확인할 수 있다.
number = int(input())
dp = [0] * 1001
dp[1], dp[2] = 1, 3
for num in range(3, number+1):
dp[num] = 2 * dp[num-2] + dp[num - 1]
print(dp[number] % 10007)