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

문제 설명

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

제한사항

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

---

입출력 예

n	result
2	2
3	5

입출력 예 설명

입출력 예 #1
2개의 괄호쌍으로 [ (()), ()() ]의 2가지를 만들 수 있습니다.
입출력 예 #2
3개의 괄호쌍으로 [ ((())), (()()), (())(), ()(()), ()()() ]의 5가지를 만들 수 있습니다.

풀이)

dfs를 이용해 뒤에서부터 괄호를 추가한다고 생각해서 푼 문제이다.

즉, 닫힘 괄호 기호(")")부터 하나씩 추가하고 닫힘 괄호 기호 수에 맞춰서 열림 괄호 기호("(")를 추가했다.

닫힘 괄호 기호와 열림 괄호 기호가 n개라면 짝이 맞는다는 얘기니깐 올바른 괄호가 된다.

주의점

열림 괄호 기호 수가 닫힘 괄호 기호 수를 넘어가면 안된다.

코드)

#include <string>
#include <vector>

using namespace std;
int result =0;

void dfs(int close,int open,int n){
    if(close == 0 && open == n){
        result++;
        return;
    }
    if(close > 0) dfs(close-1,open,n);
    if(n-close > open) dfs(close,open+1,n);
}

int solution(int n) {
    dfs(n,0,n);
    return result;
}