[C++][백준 12919] A와 B 2

[문제]

12919번: A와 B 2 (acmicpc.net)

12919번: A와 B 2

[문제 풀이]

처음에는 recursive()함수를 이용해서 S에서 T로 이동하는 방식으로 풀었는데 해당 방식으로는 시간 초과가 일어났다.

이유는 A에서 B로 가는 경우는 계속해서 2씩 추가되면서 T의 길이인 2^50가지의 경우가 생길 수 있기 때문이다.

하지만 반대로, B에서 A로 가는 경우를 보면 매 경우에 2씩 추가되지가 않는다.

B가 앞에 없는 경우가 있거나 A가 뒤에 없는 경우에는 해당 경우를 패스하고 종료가 되기 때문에 0이 나오고 하나밖에 없는 경우라면 하나만 되니까 2씩 추가가 되지 않는다.

그렇기에 반대로 유추해보면 시간복잡도에서 시간초과가 걸리지 않는다는 것을 알 수가 있다.

[회고]

예전에 못풀었었던 문제인데 3번째 도전으로 풀었다.

예전보다 확실히 재귀에 대한 이해도가 높아졌는지 문제를 보자마자 재귀에 대해서 생각이 도달할 수 있었다.

다만, 재귀에서 일어나는 시간복잡도에 대해서 주의할 필요가 있을듯.

[코드]

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

using namespace std;

string s,t;
int answer = 0;
void recursive(string str){
    if(str.size() == s.size()){
        if(str == s){
            answer = 1;
            return;
        }
        return;
    }

    if(str[0] == 'B'){
        string temp;
        for(int i = str.size() - 1;i>0;i--){
            temp += str[i];
        }
        recursive(temp);
    }
    if(str[str.size() - 1] == 'A'){
        string temp;
        for(int i = 0;i<str.size() - 1;i++){
            temp += str[i];
        }
        recursive(temp);
    }
    return;
}

int main(){
    cin>>s>>t;
    recursive(t);
    cout<<answer<<endl;

    return 0;
}