4811 알약

#include <iostream>

using namespace std;

int pills[1000] {};
int numPills;
long long catalanNum[31] {};

long long catalan(int num)
{
    if (num < 2) {
        catalanNum[num] = 1;
        return 1;
    }
    if (num == 2) {
        catalanNum[num] = 2;
        return 2;
    }
    if (catalanNum[num] != 0) {
        return catalanNum[num];
    }
    for (int i = 0; i < num; i++) {
        catalanNum[num] += catalan(i) * catalan(num - 1 - i);
    }

    return catalanNum[num];
}

void solve()
{
    for (int i = 0; i < numPills; i++) {
        cout << catalan(pills[i]) << endl;
    }
}

void input()
{
    while (true) {
        cin >> pills[numPills];
        if (pills[numPills] == 0) break;
        numPills++;
    }
}

int main(void)
{
    input();
    solve();

    return 0;
}

솔직히 말하면 나타나는 수열을 10번째항 까지 적으면 점화식을 알아낼 줄 알았다.

하지만 4번째 수 부터 엄청난 속도로 증가해서 당황했다.

어떤 수열인지 궁금해서 찾아보니 '카탈랑 수'라는 새로운 개념을 알아냈다.

 

카탈란수는 잘 짜인 괄호 등 여러 문제를 해결할때 나타나는 수이다(출처: suhak.tistory.com/77)

일반항을 생각보다 쉽게 구할 수 있는데 반복되는 수가 많으니 다이나믹 프로그래밍 방법으로 해결했다.