[프로그래머스] 올바른 괄호의 갯수

https://school.programmers.co.kr/learn/courses/30/lessons/12929?language=cpp

프로그래머스

프로그래머스 - 올바른 괄호의 갯수

문제 유형 - 다이나믹 프로그래밍, 조합론, 수학, 카탈란 수

문제 난이도 : Level 4

 

문제 설명

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

제한사항

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

 

 

풀이

0개의 괄호로 만드는 조합은 빈 문자열로 1개입니다.
1개의 괄호로 만드는 조합은 "()" 1개입니다.
2개의 괄호로 만드는 조합은 "(())"과 "()()", 2개입니다.
3개의 괄호로 만드는 조합은 "**()** (())", "**()** ()()", "**(())** ()", "**(()())** ", "**((()))** "으로 5개입니다.

모든 prefix에서 ')'의 개수는 '('의 개수보다 항상 더 많을 수 없고, 총 '(', ')'의 개수는 똑같아야 합니다.
그래서, 첫 번째에는 반드시 '('이 와야 합니다.
그러고, 첫 번째 괄호를 닫기 위한 짝인 ')'가 어딘가에 있어야 합니다.

이 첫 번째 괄호쌍의 속과 그 뒤에 유효한 괄호쌍을 채우는 식으로 구성됩니다.
그래서, n개로 조합을 만들려면, 첫 괄호쌍을 열고, n-1개로 두 부분(첫 괄호안, 첫 괄호뒤)에 나눠서 유효한 괄호쌍으로 채우면 됩니다.
그래서 dp[4]인경우는, 다음과 같이 구성됩니다.
```
dp[0] * dp[3] + // 첫 괄호안에 0개쌍, 그 뒤에 3개쌍이 붙은 경우
dp[1] * dp[2] + // 첫 괄호안에 1개쌍, 그 뒤에 2개쌍이 붙은 경우
dp[2] * dp[1] + // 첫 괄호안에 2개쌍, 그 뒤에 1개쌍이 붙은 경우
dp[3] * dp[0] // 첫 괄호안에 3개쌍, 그 뒤에 0개쌍이 붙은 경우
```
즉, dp[i] = sum of(dp[j] + dp[i - j - 1]) for j in range in range [0, i)가 됩니다.

 

 

 

코드

C++

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;
    
    for(int i = 4; i <= n; i++) {
        for(int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i-j-1];
        }
    }
    return dp[n];
}

 

GO

func solution(n int) int {
    dp := make([]int, 15, 15)
    dp[0] = 1;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 5;
    
    for i := 4; i <= n; i++ {
        for j := 0; j < i; j++ {
            dp[i] += dp[j] * dp[i-j-1]
        }
    }
    return dp[n]
}