백준 12904번 A와 B [C++]

 

 

#문제 해결 방법

 

가장 중요한 생각은

S ->T로 가는건 가지수가 많기 때문에

시간초과가 나기 매우매우 쉽다는것이다.

혹시 하더라도 일치하는지 확인하는 조건때문에 kmp 가 필요할지도 모르겟다.

 

때문에 T->S 로 가는 것은 매우 가지수가 적다.

왜냐면 뒤에 A가 있다면 A를 추가한것이기 때문에 빼주고

B가 잇다면 B를 뒤집고 추가해준거라 빼고 뒤집어 주면된다

 

이 힌트를 알 수 있는것은

바로 추가하는 방향이 한쪽으로만 이뤄진다는 것이다.

 

만약 양방향으로 추가가 되었다면 불가능했을 것이다.

 

#전체 코드

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;





int main() {
    string s,t;
    cin >> s >> t;



    while (true) {

        if (t[t.length() - 1] == 'A') {
            t.pop_back();
        }
        else {
            t.pop_back();
            reverse(t.begin(), t.end());
        }

        if (t.length() == s.length()) {
            if (s == t) {
                cout << 1 << '\n';
            }
            else {
                cout << 0 << '\n';
            }
            break;
        }
    }


    return 0;
}