[BOJ] 백준 1670 - 정상 회담 2

문제 링크

www.acmicpc.net/problem/1670

1670번: 정상 회담 2

 

풀이

백준 17268 - 미팅의 저주 문제와 입력도, 출력도, 코드도 똑같습니다.

카탈란 수를 구해주면 됩니다.

 

 

정답 코드

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
#define MOD 987654321LL

ll d[5001] = { 1 };
int n;
int main() {
	cin >> n;
	n /= 2;
	for (int i = 1; i < n + 1; i++) {
		for (int j = 0; j < i; j++) {
			d[i] += (d[j] % MOD) * (d[i - 1 - j] % MOD) % MOD;
			d[i] %= MOD;
		}
		d[i] %= MOD;
	}

	cout << d[n];
}