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

문제를 보고 점화식을 세우다가 dp이고, dp[0]x?? + dp[1]x?? + ... 인 것 까진 발견했는데, 그 이상 진전이 없어서 구글링을 좀 했다...

알고보니 카탈란수라는 점화식으로 구할 수 있는 문제였다.

예를 들어,
C0 = 1
C1 = C0 x C0
C2 = C0 x C1 + C1 x C0
C3 = C0 x C2 + C1 x C1 + C2 x C0
이렇게 되는 것이다.

왜 카탈란 수인지 생각해보면
A는 n - k - 1 번째, B는 k번째 올바른 괄호의 집합이라 생각해보면 이 둘을 다음과 같은 식으로 합칠 수 있다.

C = (A)B (C는 n번째 올바른 괄호의 집합)

또한 A의 위치에 0, 1, 2, ... n - 1까지 가능하고, B는 반대로 n - 1, n - 2, ... 0까지의 순소로 가능한데, 이는 카탈란 수의 성질을 띈다.

코드는 아래와 같다.

// 카탈란수로 구현한 결과
#include <string>
#include <vector>

using namespace std;

int answer = 0;
int dp[20] = { 1 };
void catalan(int n) 
{
    int sum = 0;
    for(int i=0;i<n;i++) 
        sum += dp[i] * dp[n-i-1];
    dp[n] = sum;
}
int solution(int n) {
    
    for(int i=1; i<=n; i++) 
        catalan(i);
    answer = dp[n];
    
    return answer;
}

카탈란수로 구현한 결과

카탈란수로 구현한 후 다른 분들의 코드를 보다가 DFS로 된다는 것을 발견하고, 바로 구현해봤다.
open을 n부터 시작해서 빼는 분들도 많던데, 의미상 0부터 시작해도 되는 것 같다.

원리는 여는 괄호, 닫는 괄호의 전체 가능 경우의 수를 구하면서 빠르게 가지치기 하는 것인데,
만약 여는 괄호보다 닫는 괄호의 갯수가 많거나, 혹은 여는 괄호 혹은 닫는 괄호가 절반 이상이 되면 그로부터 파생되는 DFS 들은 필요없으니 수행하지 않는다(올바른 괄호에서 시도했던 최적화와 비슷하다).

그렇게 DFS를 돌면서 만약 여는 괄호와 닫는 괄호의 총 갯수가 n이 되고, 둘의 갯수가 같으면 정답을 더해준다.

당연히 모든 경우의 수를 다 구하기 때문에 N이 커질수록 카탈란 수보다는 그 시간이 더 오래 걸린다.

#include <string>
#include <vector>

using namespace std;

int answer = 0;

void dfs(int open, int close, int n, int depth)
{
    if(close > open)
        return;
    
    if(close > n / 2 || open > n / 2)
        return;
    
    if(open == close && open + close == n) 
        answer++;
    
    dfs(open + 1, close, n, depth + 1);
    dfs(open, close + 1, n, depth + 1);
}
int solution(int n) {
    dfs(0, 0, n << 1, 0);
    return answer;
}

DFS로 구현한 결과