[Java] 백준 1670번 정상 회담 2

다이나믹 프로그래밍 문제입니다.

결과값이 카탈란 수 수열과 동일합니다. (1, 1, 2, 5, 14 ...)
카탈란 수 수열을 계산해서 결과값을 출력할 수도 있습니다.

DP를 사용해서 문제를 풀었습니다.
첫번째 사람을 기준으로 문제에 접근합니다.
첫번째 사람이 이어진 경우 2개의 그룹으로 나누어 질 수 있습니다.
2개의 그룹에 대한 경우의 수를 곱해서 결과값을 출력합니다. 
이때 2개의 그룹에 대한 경우의 수는 DP로 계산되어있습니다.

4명일때
1-2번이 이어지면 3,4번이 남습니다.
이는 DP[0] * DP[2]로 나타낼 수 있습니다. (그룹1 = 0명, 그룹2 = 2명)
1-4번이 이어질 경우 2,3번이 남습니다.
마찬가지로 DP[0] * DP[2]로 나타낼 수 있습니다
위의 2값을 더한 값이 DP[4]가 됩니다.

6명일때
1-2번이 이어지면 3,4,5,6이 그룹이 됩니다.
=> DP[0] * DP[4]
1-4가 이어지면 2,3 / 5,6으로 2그룹으로 나누어집니다.
=> DP[2] * DP[2]
1-6가 이어지면 2,3,4,5이 그룹이 됩니다.
=> DP[0] * DP[4]
위의 3개의 결과값을 더한 값이 DP[6]이 됩니다.

위와 동일한 방식으로 찾는 값이 될 때까지 DP값을 bottom-up방식으로 구합니다.

주의할점은 수의 범위가 크므로 int형이 아닌 long형으로 DP배열을 만들었습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(br.readLine());
		long[] DP = new long[n + 1];

		DP[0] = 1;
		DP[1] = 0;

		for (int i = 2; i <= n; i += 2) {
			for (int j = 0; j < i / 2; ++j) {
				DP[i] += (DP[0 + (j * 2)] * DP[i - 2 - (j * 2)]) % 987654321;
				DP[i] %= 987654321;
			}
		}
				
		bw.write(DP[n] + "\n");
		bw.close();
	}
}