[프로그래머스] 올바른 괄호의 갯수 Java 풀이 (카탈란수)

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

위 문제가 DP문제인것은 눈치채기가 쉬운데 도저히 규칙히 찾아지지가 않았다. 찾아보니 대표적인 카탈란수 문제였다.

문제 풀이

카탈란수를 간략하게 설명하면 짝이 주어질때의 경우의 수를 나열한 수열이다. 위 괄호는 “(” 가 나올때 뒤에 무조건 “)” 가 나와야 하고

 

아래 산문제도 짝이 “/” 이 나오면 “\” 나와야하는 짝이 있어야하므로 대표적인 카탈란 수 문제이다.

그래서 대표적인 점화식이 존재한다. 원래 DP문제는 점화식을 찾아야하는 문제인데 카탈란 수 문제인걸 알면은 점화식을 바로 알수가 있다.

점화식은 아래와 같다. 이 점화식을 이용하여 문제를 풀면 된다.

코드

public int solution(int n) {
    int dp[] = new int[n + 1];
    dp[0] = 1;
    dp[1] = 1;

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

    return dp[n];
}

참조 : https://suhak.tistory.com/77