문제

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

입출력

입력

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

출력

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

예시

---

해설

2x1 일때는 ? 1개
2x2 일때는? 2개
2x3 일때는? 3개
2x4 일때는? 5개
2x5 일때는? 8개

점화식 dp[N] = dp[N-1]+dp[N-2]

점화식 (알못식 설명 주의)

어떤 값이 이전 값에 의해 정해지는 식
다이나믹 프로그래밍에 쓰인다.

다이나믹 프로그래밍

큰 문제를 풀기 위해 작은문제부터 품

점화식이란 이전 값에 의해 현재 값이 정해지는 식
그렇다면 이전 값은 중복해서 나오게 된다.

• dp[N] = dp[N-1]+dp[N-2]을 예로 들자면, dp[5]룰 위해 dp[4]와 dp[3]이 쓰인다. 그리고 dp[6]을 위해 dp[5]와 dp[4]가 쓰인다.
  => dp[4]가 중복하여 쓰인다.

지금은 수가 작아서 괜찮지만 커질수록 느려진다.

그런 불상사를 막고 싶다면 중복되는 결과를 저장할 필요가 있다.
=> 메모이제이션

코드

2x3부터 점화식 적용

#입력
n=int(input())

# 2x1 ~ 2x1000 범위의 모든 타일의 경우의 수 넣을 리스트
dp = [0]*1001

# 2x1의 경우의 수는 1이다.
dp[1]=1
# 2x2의 경우의 수는 2이다.
dp[2]=2

# 2x1000까지 경우의 수 계산ㅉ
for i in range(3, n+1):
    dp[i]=dp[i-1]+dp[i-2]

print(dp[n]%10007)

#다이나믹 프로그래밍