문제

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력

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

출력

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

예제 입력 1

2

예제 출력 1

3

예제 입력 2

8

예제 출력 2

171

예제 입력 3

12

예제 출력 3

2731

풀이

dp 로 푸는 유형이라 판단했고, 쉽지는 않았지만 점화식을 찾을 수 있었다.
dp 는 점화식이 대부분 존재하므로 점화식을 찾으려 노력하는게 중요한 것 같다. 찾은 점화식: dp[n] = dp[n-1] + 2*dp[n-2]

10007 로 나눈 나머지를 구하는 것인데, dp 배열의 원소 크기를 줄이기 위해 dp 의 원소값을 처음부터 계속해서 10007로 나눠주었다.

왜냐하면 나머지의 특성에 의해, 마지막에 10007 로 나눈 나머지를 구하는 것이나 처음부터 dp 에 10007 로 나눈 값들을 쌓아가는 것이나 구하고자 하는 값은 같기 때문이다.

예시
1, 2, 3, 5, 8, 13, 21, 34 의 순서로 점화식 dp[n] = dp[n-1] + dp[n-2]의 값이 있다고 할때, 마지막 값을 20으로 나눈 나머지를 구한다고 해보자.

값을 일반적으로 다 구하고 마지막에 20으로 나눈 경우는 dp 배열의 원소가 위와 같이 그대로 들어가게 되고, 구하고자 하는 값은 34 % 20 = 14 이다.
그러나 처음부터 dp 의 값을 계속해서 20으로 나눠주는 경우는 다음과 같이 원소가 구성되게 된다.
1, 2, 3, 5, 8, 13, 1, 14
결국 배열의 원소의 크기를 줄이면서도 구하고자 하는 값(14)은 그대로 구할 수 있게 된다.

풀이

n = int(input())
dp = [0 for _ in range(1001)]
dp[0], dp[1], dp[2], dp[3] = 0, 1, 3, 5

for i in range(3,n+1):
    dp[i] = (dp[i-1] + 2*dp[i-2]) % 10007

print(dp[n])