[BOJ/백준][Gold5] 12919 : A와 B 2 (C++)

https://www.acmicpc.net/problem/12919

12919번: A와 B 2

 

 

[난이도] Gold5
[유형] 브루트포스

[풀이]
S에서 T를 만드려고 하면 모든 문자에서 두가지 연산을 다 해봐야 하기 때문에 시간초과가 발생합니다.
역으로 T에서 S로 원복시키는 방식으로 하면 각 연산을 적용할 수 없는 경우가 생기기 때문에
많은 케이스가 가지치기 됩니다.
그러므로 재귀함수로 T에서 S를 만들 때 가능한 모든 경우의 수를 구해서 체크해주면 됩니다.

 

#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
string S,T;
bool ok;
void sol(string s){
    if(s==S){
        ok=1;
        return;
    }
    if(s.size()<=S.size()) return;
    if(s.front()=='B'){
        string tmp = s;
        reverse(tmp.begin(),tmp.end());
        tmp.pop_back();
        sol(tmp);
    }
    if(s.back()=='A'){
        s.pop_back();
        sol(s);
    }
}
int main(){
    cin >> S >> T;
    sol(T);
    cout << ok;
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/12919.cpp