이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 메모라이제이션을 2*1, 1*2, 2*2를 가장 왼쪽이 붙이는 경우로 나눠서 진행하였다.

• 2*1로 시작하는 타일링의 경우 이전의 모든 경우를 더한 수가 된다
• 1*2로 시작하는 타일링의 경우 이전의 1*2의 경우의 수와 같다.
• 2*2로 시작하는 타일링의 경우 이전의 1*2의 경우의 수와 같다.

dp[0][i]를 2*1, dp[1][i]를 1*2, dp[2][i]를 2*2로 설정하였다. 이를 점화식으로 나타내면 다음과 같이 나타낼 수 있다.

dp[0][n]=dp[0][n-1]+dp[1][n-1]+dp[2][n-1]
dp[1][n]=dp[0][n-1]
dp[2][n]=dp[0][n-1]

결과는 dp[0][n]+dp[1][n]+dp[2][n]의 값이다.

• n을 입력받는다.
• dp배열을 3*(n+1)의 크기로 0을 채워 선언한다.
• dp[0][1]을 1로 갱신한다. (2*1 타일링의 경우 2*1 타일로만 채울 수 있으므로)
• 2부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> dp[0][i]를 (dp[0][i-1]+dp[1][i-1]+dp[2][i-1])%10007로 갱신한다.
  -> dp[1][i]와 dp[2][i]를 dp[0][i-1]로 갱신한다.
• (dp[0][n]+dp[1][n]+dp[2][n])%10007을 출력한다.

Code

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