[programmers] 올바른 괄호의 갯수

https://school.programmers.co.kr/learn/courses/30/lessons/12929

프로그래머스

 

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dfs

 

---------------------------------------------------풀이----------------------------------------------------

 

괄호 쌍의 개수를 케이스를 나누어가며 모든 경우의 수를 계산하는 문제였다.

dfs()함수에서는 총 괄호쌍의 개수 n, 여는 괄호의 개수 open, 닫는 괄호의 개수 close를 인자로 넘겨준다.

맨 처음에는 무조건 여는 괄호가 나와야하므로 초기값으로는 n, open=1, close=0을 넘겨준다.

 

우선, 종료조건이다. ans에 가능한 경우의 수를 저장해 리턴할 건데, open의 개수와 close의 개수가 모두 n이면,

즉, 모든 괄호쌍이 다 나왔고 제대로 닫았으면 맞는 케이스 하나로 취급해 1을 리턴한다.

 

이후에는 open과 close를 사용할 수 있는 조건에 따라 dfs()를 계속 호출한다.

괄호를 열 수 있는 케이스는 open의 값이 괄호쌍의 개수 n보다 작아야만 가능하다.

그럼 무조건 열 수 있다.

 

괄호를 닫을 수 있는 케이스는 close의 값이 open의 값보다 작아야만 가능하다.

즉, 열린 괄호에 대해서만 닫을 수 있다.

#include <string>
#include <vector>
#include <iostream>

using namespace std;

// 총 괄호쌍의 개수, 열린 개수, 닫힌 개수
int dfs(int n, int open, int close){
    int ans = 0;
    
    // 모든 괄호쌍을 닫았으면 케이스+1
    if(open == n && close == n){
        ans++;
        return ans;
    }
    
    // open을 할 수 있는 케이스
    // open이 n보다 작아야 함.
    if(open < n){
        ans += dfs(n, open+1, close);
    }
    
    // close를 할 수 있는 케이스
    // open이 close보다 많으면 close를 할 수 있음
    if(open > close){
        ans += dfs(n, open, close+1);
    }
    
    return ans;
}

// 괄호 쌍의 개수 n. ()->1개 ()()->2개
// n개의 괄호 쌍으로 만들 수 있는 괄호 문자열의 개수=?
// 1<=n<=14
int solution(int n) {
    return dfs(n, 1, 0);
}

 

---------------------------------------------------후기----------------------------------------------------

 

진짜 간단하게 완탐으로 풀리는데

왜 level 4.....????

이해가 안된다. 뭔가 이상해!