문제
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.
아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
출력
첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.
나의 코드
import sys
input = sys.stdin.readline
n=int(input())
dp=[0]*1001
dp[1]=1
dp[2]=2
for i in range(3,n+1):
dp[i]=(dp[i-2]+dp[i-1])%10007
print(dp[n])
#dp[i]는 dp[i-2]에서 끝에 가로줄 1*2모양의 직사각형2개를 놓는 경우와
#dp[i-1]의 끝에 세로줄 2*1모양의 직사각형 1개를 놓는 경우의 합이다.수행시간: 80ms
내 생각
dp[i]는 2xi의 직사각형을 만드는 경우의 수인데 이는 2x(i-2)의 직사각형들에다가 1x2의 직사각형2개를 붙이는 경우와 2x(i-1)의 직사각형들에다가 2x1의 직사각형 1개를 붙이는 경우이다.
따라서 dp[i]=dp[i-1]+dp[i-2]
