이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 우선 점화식을 구하기 위해 도식화해보았다.

y축은 가장 왼쪽 타일의 경우를 5가지로 나눈 것이고, x축은 N을 의미한다. dp리스트에 저장했다고 가정한다. 우선 N이 홀수일 경우에는 주어진 타일들로 완전히 채울 수 없기 때문에 0으로 존재한다. N=6일 때부터 살펴보면 dp[0][6], dp[1][6], dp[2][6]는 각각 dp[:][4]의 모든 값들의 합으로 값이 갱신되는 것을 볼 수 있다. 그림에는 없지만 N=8일 경우에는 dp[:][6]에 dp[3][4], dp[4][4]의 값도 더해진 값으로 갱신된다.

이 과정을 간단하게 생각해보면 dp를 1차원 리스트로도 표현이 가능하다. dp[0]을 1로 설정하게 되면 다음과 같은 패턴으로 값이 증가한다.

dp[0]	dp[2]		dp[4]			dp[6]
1	(1*3)+(0*2)=3	(3*3)+(1*2)+(0*2)=11	(11*3)+(3*2)+(1*2)+(0*2)=41

이 패턴을 통해 점화식을 구해보면 다음과 같은 과정으로 구할 수 있다.

• dp[4] = dp[2]*3 + (dp[0]*2)
• dp[6] = dp[4]*3 + (dp[2]*2 + dp[0]*2)
• dp[8] = dp[6]*3 + (dp[4]*2 + dp[2]*2 + dp[0]*2)
  ...
• dp[n] = dp[n-2]*3 + (dp[n-4]*2 + dp[n-6]*2 + ... + dp[0]*2)

점화식은 dp[n] = dp[n-2]*3 + (dp[n-4]*2 + dp[n-6]*2 + ... + dp[0]*2) 이다.

• n을 입력받는다.
• dp 리스트를 n+2개의 0으로 채운다.
• dp[0]을 1로, dp[2]를 3으로 갱신한다.
• 4부터 n까지 2씩 증가하는 i에 대한 for문을 돌린다.
  -> dp[i]를 dp[i-2]에 3을 곱한 값으로 갱신한다.
  -> 4부터 i까지 2씩 증가하는 j에 대한 for문을 돌린다.
  --> dp[i]에 dp[i-j]를 2 곱한 값을 더한다.
• dp[n]을 출력한다.

Code

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