[Algorithm] ๐Ÿ–ฝ๋ฐฑ์ค€ 2133 ํƒ€์ผ ์ฑ„์šฐ๊ธฐ

HaJingJingยท2021๋…„ 6์›” 25์ผ
0

Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
79/119

0. ๋ฌธ์ œ

3ร—N ํฌ๊ธฐ์˜ ๋ฒฝ์„ 2ร—1, 1ร—2 ํฌ๊ธฐ์˜ ํƒ€์ผ๋กœ ์ฑ„์šฐ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•ด๋ณด์ž.

์ž…๋ ฅ
์ฒซ์งธ ์ค„์— N(1 โ‰ค N โ‰ค 30)์ด ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ
์ฒซ์งธ ์ค„์— ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

1. ์•„์ด๋””์–ด

๐Ÿ’ก ํ™€์ˆ˜๋Š” ๋ฌด์กฐ๊ฑด 0
๐Ÿ’ก ๊ด€๊ณ„ ํŒŒ์•…ํ•˜์—ฌ ์ ํ™”์‹ ๊ตฌํ•˜๊ธฐ
dp[i] = dp[i-2]dp[2] + dp[j]2 (j = 0 ~ i-4)

2. ํ•ต์‹ฌ ํ’€์ด

  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;
}

3. ์ฝ”๋“œ

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]);
	}

}

4. ๊ฒฐ๊ณผ

์„ฑ๊ณตโœจ

profile
๐ŸŒฑ์ดˆ๋ณด ๊ฐœ๋ฐœ์ž๐ŸŒฑ

0๊ฐœ์˜ ๋Œ“๊ธ€