2*n 타일링

해당 문제는 2n크기의 직사각형을 12, 2*1 타일로 채우는 방법의 수를 구하는 것이다.
Bottom-Up 방식으로 점화식을 설계 해보고자 했다.

우선 dp배열에 대해서는 아래와 같이 설정을 했다.

dp[i]: 길이가 2*i인 직사각형에 1*2, 2*1 타일을 채울 수 있는 방법의 수

그래서 아이패드에 타일을 하나씩 그리며 채워보고 있었다.
그러면서 점화식을 발견하게 되었다.(필자는 그림을 잘 못그리는 편...)

위 그림의 핵심은 N이 3인 경우이다.
이 경우에 N이 1인 경우에서 21 타일을 채우고, N이 2인 경우에서 12 타일을 채우면 되는 것이었다.

혹시나 해서 N이 4인 경우에도 진행을 했다.
마찬가지로 N이 2인 경우에서 21 타일을 채우고, N이 3인 경우에서 12 타일을 채우면 됐다.

그래서 나온 점화식은 아래와 같다.

dp[i] = dp[i-1] + dp[i-2]

그러므로 나는 소스코드를 다음과 같이 설계했다.

import sys

N = int(sys.stdin.readline().strip())
dp = [0 for _ in range(N + 2)]

dp[1] = 1
dp[2] = 2

for i in range(3, N + 2):
    dp[i] = dp[i - 1] + dp[i - 2]  # dp[i-1]배열에 1*2 타일, dp[i-2]배열에 2*1 타일

print(dp[N] % 10007)