/ BOJ

BOJ_1670_정상회담2_JAVA

문제 : 정상회담2

링크 : BOJ_1670_정상회담2

접근 방식

카탈란 수 문제는 이 문제가 카탈란 수로 풀 수 있다는 것을 미리 파악하는 것이 포인트인 것 같다.

이 문제 역시 짝수의 경우에 카탈란 수의 수열로 진행되는 문제로, 카탈란 수의 dp로 풀이하면 쉽게 풀 수 있는 문제였다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_1670_정상회담2 {

	static final int MOD = 987654321;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		long[] dp = new long[10001];

		dp[0] = 1;
		dp[2] = 1;

		int N = Integer.parseInt(in.readLine());

		for (int i = 4; i <= N; i += 2) {
			for (int j = 0; j < i-1; j+=2) {
				dp[i] += dp[j] * dp[(i - 2 - j)];
				dp[i] = dp[i] % MOD;
			}
		}

		System.out.println(dp[N]);

	}
}

괄호 문제와 비슷한 짝수에서의 카탈란 수 문제였다.