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

문제 설명

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

제한사항

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

---

풀이

실패
문제의 조건을 보고 n의 범위가 작은 것을 확인하여서 백트래킹을 이용해서 풀 수 있겠다는 생각이 바로 들었다. 하지만 이 문제가 4-level인 이유는 이 풀이가 아니라 다른 수학적 접근을 원한다고 생각했고, 점화식을 구했지만 틀렸다… 찾아보니 해당 문제는 카탈란 수라는 수학 개념을 사용하는 문제였다.
너무 낯선 개념이었지만, 막상 점화식을 보니 왠지 꽤 많이 접한 것 같은 익숙함이 느껴졌다(!?) 카탈란 수에 대해서 아주 잘 정리된 블로그 주소를 하단에 첨부하였다.

백트래킹으로는 매우 간단하게 풀이가 가능하다.

DFS 코드

#include <string>

using namespace std;

int n, ans;

void dfs(int val, int cnt){
    if(cnt == 2*n){
        if(val == 0) ++ans;
        return;
    }
    
    dfs(val + 1, cnt + 1);
    // 짝이 맞는 '('가 있어야만 ')' 추가
    if(val > 0) dfs(val - 1, cnt + 1);
}
    
int solution(int _n) {
    ans = 0;
    n = _n;
    // 시작은 반드시 여는 괄호 '('
    dfs(1, 1);
    return ans;
}

참고문헌

https://suhak.tistory.com/77