[프로그래머스 C#] Lv.4 올바른 괄호의 갯수

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

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

어느 한 괄호 안에 n개의 괄호쌍이 들어간다면, n개의 괄호쌍으로 만들 수 있는 모든 괄호 문자열이 들어갈 수 있으므로, DP문제라고 유추할 수 있음 -> 점화식 구하는 문제

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

DP[1] = 1쌍의 괄호의 경우는 1가지 ()

DP[2] = 2쌍의 괄호의 경우는 2가지 ()(), (())

DP[3] = 3쌍의 괄호의 경우는 5가지 (중요)

- 안에 2개의 괄호, 밖에 0개의 괄호 ((())), (()()) = DP[2] * DP[0]

- 안에 1개의 괄호, 밖에 1개의 괄호 (())()          = DP[1] * DP[1]

- 안에 0개의 괄호, 밖에 2개의 괄호 ()(()), ()()() = DP[0] * DP[2]

( 곱셈 연산이 들어가기 때문에 DP[0]은 1로 계산 )

 

DP[n] = DP[0]*DP[n-1] + DP[1]*DP[n-2] +ㆍㆍㆍ+ DP[n-1]*DP[0] ( DP[0] = 1 )

ex) DP[4] = DP[3]*DP[0] + DP[2]*DP[1] + DP[1]*DP[2] + DP[0]*DP[3] = 5 + 2 + 2 + 5 = 14

 

이는, 카탈란 수인데, 이와 관련된 더 자세한 내용은 하단 블로그 링크 참조

https://plusthemath.tistory.com/445

[더플러스수학] 카탈란 수 - 점화식(3)

정답 풀이 코드

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

            for (int i = 2; i <= n; i++)
            {
                int num = i - 1;

                for (int j = 0; j < i; j++)
                    dp[i] += dp[j] * dp[num - j];
            }
            
            return dp[n];
        }
    }