올바른 괄호의 갯수

문제 설명

올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요.

제한사항

괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수

문제를 본다면 dp문제라는걸 생각해볼수있다. 문제는 어떤 형식으로 진행되는건지 알수가 없다는 점인데 이를 알아내기 힘들어서 다른사람의 설명을 보게되었다.

이러한 올바른 괄호의 갯수를 새는 방식으로 카탈란 수라는것이 존재하며 그 점화식은 다음과 같다.
dp[n] = dp[0]dp[n-1]+dp[1]dp[n-2]...+dp[n-1]*dp[0];

이 점화식을 토대로 DP를 만들면 된다.

코드

class Solution {
    public int solution(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[0] = 1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                dp[i] += dp[i-j] * dp[j-1];
            }
        }
        int answer = dp[n];
        return answer;
    }
}