3รN ํฌ๊ธฐ์ ๋ฒฝ์ 2ร1, 1ร2 ํฌ๊ธฐ์ ํ์ผ๋ก ์ฑ์ฐ๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํด๋ณด์.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N(1 โค N โค 30)์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ๊ฒฝ์ฐ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ก ํ์๋ ๋ฌด์กฐ๊ฑด 0
๐ก ๊ด๊ณ ํ์
ํ์ฌ ์ ํ์ ๊ตฌํ๊ธฐ
dp[i] = dp[i-2]dp[2] + dp[j]2 (j = 0 ~ i-4)
dp[0] = 1;
dp[2] = 3;
for(int i=4; i<n+1; i+=2) {
dp[i] = dp[i-2]*dp[2];
for(int j=0; j<=i-4; j+=2)
dp[i] += dp[j]*2;
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class DP_16 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
if(n == 0 || n % 2 == 1) {
System.out.println(0);
return;
}
int[] dp = new int[n+1];
dp[0] = 1;
dp[2] = 3;
for(int i=4; i<n+1; i+=2) {
dp[i] = dp[i-2]*dp[2];
for(int j=0; j<=i-4; j+=2)
dp[i] += dp[j]*2;
}
System.out.println(dp[n]);
}
}
์ฑ๊ณตโจ