[BOJ 1670 // C++] 정상 회담 2

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1670번 문제인 정상 회담 2이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/1670 

1670번: 정상 회담 2

2N명의 대표가 모여있고, 그 중 한 소국가의 대표 A를 정하여 상황을 분석해보자.

 

이 대표가 어떤 후보와 악수를 하느냐에 따라, 양쪽으로 0 / 2N-2, 2 / 2N-4, 4 / 2N-6, ... , 2N-2 / 0명의 대표들이 있는 상황이 생길 것임을 알 수 있다. (홀수/홀수로 나누어진다면 악수를 하지 못하는 대표들이 생긴다.)

 

각 상황의 경우를 X / Y 로 나타낸다면, 구하는 경우의 수는 X명의 대표가 악수를 하는 경우의 수와 Y명의 대표가 악수를 하는 경우의 수의 곱들을 모두 합한 것으로 계산할 수 있을 것임을 알 수 있다. (이 점화식을 만족하는 수는 카탈란 수(Catalan Number)임이 잘 알려져있으나, 나누는 수 987654321은 소수가 아니므로 modulo에 대한 역원을 이용한 조합계산을 이용하기는 어렵다.)

 

위의 점화관계를 이용하여 dp를 하면 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

long long dp[5001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	dp[0] = 1;

	int N; cin >> N;
	N /= 2;

	for (int i = 1; i <= N; i++) {
		int L = 0, R = i - 1;
		while (L < i) {
			dp[i] += (dp[L++] * dp[R--]) % 987654321;
		}
		dp[i] %= 987654321;
	}
	
	cout << dp[N];
}