[BAE/<JOON> 문제풀이] 1670. 정상회담 2

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

1670번: 정상 회담 2

핵심::
카탈란 수열 문제

풀이::
카탈란 수열

 

의견::

골드 3임 이게 ( 저울 문제랑 같은 난이도 2. ??? )

 

코드::

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ull = unsigned long long;

ull dp[5002];

int main()
{
    dp[1] = 1;
    dp[2] = 1;
    for (int i = 3; i <= 5001; i++) {
        ull sum = 0;
        for (int j = 1; j < i; j++) {
            sum += (dp[j] * dp[i - j]) % 987654321;
            sum %= 987654321;
        }
        dp[i] = sum;
    }
    int n; cin >> n;
    n /= 2;
    cout << dp[n + 1];

    return 0;
}