고추장 괄호 문자열 (feat. 백준, 27967번)

고추장 괄호 문자열
https://www.acmicpc.net/problem/27967

27967번: 고추장 괄호 문자열

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int N;
string str;
bool check(){
    register int ans = 0;
    for(auto& ch : str){
        if(ch == '(')
            ++ans;
        else
            --ans;
    }
    if(ans == 0){
        cout << str;
        exit(0);
    }
    return false;
}
void dfs(register int position){
    if(position == N){
        if(!check())
            return;
    }
    if(str.at(position) == 'G'){
        str.at(position) = '(';
        dfs(position + 1);
        str.at(position) = ')';
        dfs(position + 1);
    }
    dfs(position + 1);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
    cin >> N >> str;
    dfs(0);
    return 0;
}
// *&)*@*

 

반응형

깊이 우선 탐색 (dfs) 를 활용하여 풀이하였습니다.