[오답노트: 카탈란 수] 백준 17268 미팅의 저주

혼자 그림 그려보면서 끙끙대다가 질문을 올렸는데 친절하신 분이 답변해주셨다.

앞쪽 부분의 개수를 정확히 구했으면 아래 싸이트에 수열을 넣고 검색해보라 하셨음.

 

 https://oeis.org/

The On-Line Encyclopedia of Integer Sequences® (OEIS®)

N = 2 $\longrightarrow$ 답 = 1

N = 4 $\longrightarrow$ 답 = 2

N = 6 $\longrightarrow$ 답 = 5

N = 8 $\longrightarrow$ 답 = 14

 

1, 2, 5, 14를 넣어보니 카탈란 수 라고 한다.

 

$i$번째 카탈란수 $C_i = {2i\choose i} - {2i\choose i+1}$ 이다.

문제의 제한에서 N은 짝수이므로

$C_{n/2} = {n\choose n/2} - {n\choose n/2+1}$을 구하면 되고,

$N \leq 10,000$ 이므로 단순 반복문으로 이항 계수를 구해도 시간복잡도가 충분하다.

 

카탈란 수의 점화식 $C_{n} = \sum_{i=0}^{n-1}{C_{i}C_{n-1-i}}$를 이용하면

이항 계수식을 이용하는 것보다 더 많은 카탈란수를 더 적은 메모리로 구할 수 있다.

 

 

정답 코드

#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];
}