[Algorithm] Programmers :: 올바른 괄호의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

int solution(int n) 
{
    if (n == 1) return 1;
 
    int dp[15] = { 0 };
    dp[0] = 1;
    dp[1] = 1;
 
    for (int i = 2; i <= n; ++i)
    {
        for (int j = 0; j < i; ++j)
        {
            dp[i] += dp[j] * dp[i - j - 1];
        }
    }
    
    return dp[n];
}

프로그래머스 AI문제추천에 있길래 한번 시도해봤는데... 일단 몇레벨인지 모르고 풀이를 시도해봤다.

DP문제인건 바로 알았는데, 나름 생각해본 점화식이 틀려서 고민하다 다른사람 풀이를 봤다.

그냥 심플하게 '카탈란 수'라는 조합에서 자주 나오는 수열규칙이였다.

 

원리도 그렇게 어렵진 않다. 내가 처음 시도했던 접근법이 완전히 틀리게 생각한건 아니라서 그런가, 이해는 매우 쉬웠다.

왼쪽에 임의의 괄호한쌍을 두는것까지는 맞게 생각했는데, 그 임의의 괄호한쌍 '안'에다가 DP값을 넣는것까지를 생각 못했다..