[ICPC] 백준 4811 - 알약

icpc.me/4811

 

N이 주어질 때 서로 다른 문자열의 개수를 $D_N$이라고 한다면 $D_1 = 1, D_2 = 2, D_3 = 5, D_4 = 14$ 가 예제 TC에 주어지고 이는 카탈란 수임을 알 수 있다.

 

N이 작으므로 카탈란 수의 점화식 $C_N = \Sigma_{i = 0}^{N - 1}C_iC_{N - 1 - i}$을 이용해 동적계획법을 수행한 후 각 쿼리에 알맞은 값을 출력하면 된다.

 

전체 코드

#include <iostream>
 
using namespace std;
using ll = long long;
 
ll dp[31];
 
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
 
    dp[0] = dp[1] = 1, dp[2] = 2, dp[3] = 5, dp[4] = 14;
 
    for (int i = 5; i <= 30; ++i)
        for (int j = 0; j < i; ++j)
            dp[i] += dp[j] * dp[i - j - 1];
    
    int n;
    cin >> n;
 
    while (n)
    {
        cout << dp[n] << '\n';
        cin >> n;
    }
}