백준 2133

package Baekjoon;

import java.util.Scanner;

public class Number2133 {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
int[] dp = new int[n+1];

int answer = 0;
if(n % 2 == 1) {  //n이 홀수일경우는
answer = 0;  //경우의수가 없으므로 바로 0을 return
} else {
dp[0] = 1;
dp[2] = 3;

for (int i=4; i<=n; i+=2) {
dp[i] = dp[i -2 ] *dp[2];
for (int j = i - 4; j>=0; j-=2) {
dp[i] += dp[j]*2;
}
}

answer = dp[n];
}

System.out.println(answer);
sc.close();


}

}