2133: 타일 채우기

• n이 홀수면 0
• 매번 새로운 모양이 2개씩 추가됨
• dp[n] = dp[n-2] * dp[2] + (dp[n-4] + ... + dp[2]) * 2 + 2

import sys

N = int(input())

dp = [0 for _ in range(N + 1)]

if N > 1:
    dp[2] = 3

    for i in range(4, N+1):
        if i % 2 == 0:
            tmp = dp[i-2] * dp[2]
            tmp += 2
            for j in range(2, i-4+1, 2):
                tmp += dp[j] * 2
            dp[i] = tmp
        else:
            continue
    print(dp[N])
else:
    print(0)