문제: https://www.acmicpc.net/problem/2133

목표:

• 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구하기

조건:

• N(1 ≤ N ≤ 30)이 주어진다.

solution 설명 :

• 경우의 수를 나눈 다음에 그것을 차곡차곡 쌓는 것이다.

• d[2]는 
  위와 같은 경우가 있다.
  이 경우의 수는 매번 3만 곱하면 된다.

• 이제 또다른 경우의 수가 있는데
  • 4일 때
    이렇게 3*4만 있을 줄 알았으나…

  

  • 6일 때
    이렇게 3*6으로 매번 새롭게 생기는 경우의 수가 나온다.

  

  • 그러므로 다음 것으로 갈 때마다 새로운 경우의 수가 나온다.

import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
d = [1] + [0] * (n)

for i in range(2, n+1, 2):
    d[i] = 3 * d[i-2]
    for j in range(0, i-4+1, 2):
        d[i] += 2*d[j]

print(d[n])