백준 12919번 A와 B 2 C++

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

12919번: A와 B 2

 

s에서 t로 한단계씩 바꾸는 것은 시간초과가 날 수 있기 때문에 거꾸로 t에서 s로 조건에 맞을때만 바꾸는 식으로 풀었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int ans = 0;

void Rec(string s, string t) {
    if (s.length() > t.length()) return;
    if (s == t) {
        ans = 1;
        return;
    }
    if (t.back() == 'A') {
        string tmp = t.substr(0, t.length() - 1);
        Rec(s, tmp);
    }
    if (*t.begin() == 'B') {
        string tmp = t;
        reverse(tmp.begin(), tmp.end());
        tmp = tmp.substr(0, tmp.length() - 1);
        Rec(s, tmp);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s, t;
    cin >> s >> t;
    Rec(s, t);
    cout << ans;
}