[백준 2133] 타일 채우기 (DP) (C/C++) (★★★)

#include <iostream>
#include <algorithm>
using namespace std;
 
int N;
int dp[35];
 
int solve(int num)
{
    if(num == 0)
    {
        return 1;
    }
    else if(num == 2)
    {
        return 3;
    }
    
    if(dp[num] != 0)
    {
        return dp[num];
    }
    
    dp[num] = solve(num-2)*3;
    
    for(int i = num; i >= 4; i -= 2)
    {
        dp[num] += solve(i-4)*2;
    }
    
    return dp[num];
}
 
int main(void)
{
//    freopen("B2133_input.txt", "r", stdin);
    
    cin >> N;
    
    if(N % 2 == 1)
    {
        cout << 0;
    }
    else
    {
        cout << solve(N);    
    }
    
    return 0;
}