문제

문제 링크 : https://www.acmicpc.net/problem/11727

풀이

DP를 이용해서 푸는 문제이다.

2 x i 크기의 직사각형을 2 x 1, 2 x 2, 1 x 2 크기의 직사각형으로 채우는 경우의 수를 구하는 점화식은 다음과 같다. dp[i] = dp[i-1] + dp[i - 2] * 2

2 x (i - 1) 크기의 직사각형에서 2 x i 크기의 직사각형을 만드는 방법은 오른쪽에 2 x 1 크기의 직사각형을 더하는 방법 밖에 없으므로, 2 x (i - 1) 크기의 직사각형에서 2 x i 크기의 직사각형을 만드는 경우의 수는 2 x (i - 1) 크기의 직사각형을 만드는 경우의 수와 같다.

2 x (i - 2) 크기의 직사각형에서 2 x i 크기의 직사각형을 만드는 방법은 오른쪽에 2 x 2 크기의 직사각형을 더하는 방법, 1 x 2 크기의 직사각형 2개를 더하는 방법이 있으므로, 2 x (i - 2) 크기의 직사각형에서 2 x i 크기의 직사각형을 만드는 경우의 수는 2 x (i - 2) 크기의 직사각형을 만드는 경우의 수에 2를 곱해준 것과 같다.

따라서 점화식 dp[i] = dp[i - 1] + dp[i - 2] * 2 가 만들어진 것이다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [0 for i in range(n)]
dp[0] = 1
if n > 1:
    dp[1] = 3


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