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

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

프로그래머스

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

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

문제 난이도 : Level 4

 

문제 설명

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

제한사항

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

 

 

풀이

양 끝에는 반드시 (와 )가 있어야 한다.

즉, n개중, n-1개로 속을 채운다고 생각하면 된다.

n-1개로 속을 채울 때, 남은 괄호를 k쌍과 n-1-k쌍으로 볼 수 있다.

그래서, 점화식은 dp[i] = dp[0] * dp[i-1] + dp[1] * dp[i-2] + ... + dp[i-2] * dp[1] + dp[i-1] * dp[0]이다.

 

dp[n]을 n개의 괄호쌍으로 만들 수 있는 조합의 수라고 하자.

dp테이블을 n+1개의 크기를 만들어서, 베이스 케이스에 대해 초기화해준 뒤, 

dp[n]까지 타뷸레이션으로 채워서 dp[n]을 반환하면 된다.

 

 

 

코드

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]
}