11726 2xn 타일링

문제

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

 

키워드 :

이문제는 처음에서 부터 하나씩 확인하면서 규칙(점화식)을 찾아보았다.

n=1 일때는 1개

n=2 일때는 2개

n=3 일때는 3개

n=4 일때는 5개였다.

 

타일들의 모양을 보면 3일때부터 n=2인 타일에 1개씩 더넣고 n=1인 타일에 2개를 넣은 모양들의 묶음이었다.

즉 dp[3]=dp[2]+dp[1] 이었고, dp[i]=dp[i-1]+dp[i-2]라고 볼 수 있었다.

다만 문제의 n은 1~1000까지였으므로 dp[1]=1로 넣어주고 n=2이상일 때만 dp[2]=2를 해주는 조건으로 

문제를 풀었다. 조금 찝찝하긴 하다

 

풀이 : 

#1 n 입력받기
n=int(input())
#dp테이블
dp=[0]*1001
dp[1]=1
if n>=2:
  dp[2]=2
  for i in range(3,n+1):
     dp[i]=dp[i-1]+dp[i-2]
print(dp[n]%10007)