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

올바른괄호의갯수 (프로그래머스 Level 4)

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

수학적 지식이 필요한 ‘조합’ 쪽 문제이지 않을까 싶었으나
제한사항의 n이 약 14 정도이기에
백트래킹 방식으로도 풀 수 있지 않을까 싶었다

set 을 통해 완성된 조합을 저장시키고
dfs와 백트래킹을 통해 이전 단계로 돌아가는 방식을 적용시켰다

문제의 조건인 ‘괄호’는 결국
‘)’ 괄호가 ‘(‘ 의 수보다 많아지면 안되기에
후방 괄호쪽의 if문에 조건을 하나 추가하여 사용하였다

• 처음에는 set을 통해 ‘조합’을 찾는 방식을 이용하였는데
  단순히 answer++를 사용하더라도 충분히 정답을 찾아낼 수 있었다
  (더 빨리 통과된 것은 덤)
  

Code

#include <string>
#include <vector>

using namespace std;

void dfs(int& answer, string& temp, int fc, int rc)
{
    // 종료 조건 (fc 와 rc가 모두 0)
    if (fc == 0 && rc == 0)
    {
        answer++;
        return;
    }
    
    // 백트래킹
    // 전방 괄호 추가
    if(fc > 0)
    {
        temp.push_back('(');
        dfs(answer, temp, fc - 1, rc);
        temp.pop_back();
    }

    // 후방 괄호 추가
    if(rc > 0 && rc > fc)
    {
        temp.push_back(')');
        dfs(answer, temp, fc, rc - 1);
        temp.pop_back();
    }
}

int solution(int n) {
    string temp = "";
    int answer = 0;
    
    dfs(answer, temp, n, n);

    return answer;
}