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

문제링크 : https://www.acmicpc.net/problem/12904

12904번: A와 B

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

string S, T;
int result;

void func()
{
    while(1)
    {
        if(S==T) 
        {
            result = 1;
            break;
        }
        else if (S.size()==T.size()) break;

        if(T[T.size()-1]=='A') T.pop_back(); //뒤 A제거
        else //뒤 B제거 후 뒤집기
        {
            T.pop_back();
            reverse(T.begin(), T.end());
        }
    }
    
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> S >> T;
    func();
    cout << result;
}

 

처음에 재귀로 풀었다가 시간초과가 발생했다.

재귀로 할 경우 매 탐색마다 reverse 함수 사용인한 시간 초과로 인해 다른 방법으로 풀어야 한다.

 

재귀로 풀 경우 S를 기준으로 만들어가는 과정을 생각했지만, T를 기준으로 S를 만드는 방법으로 풀면 수월하다.

주어진 연산을 거꾸로 생각하여 T의 맨 뒤가 A면 제거하고 B면 B를 제거후 뒤집어준다.

이를 S와 T가 같거나, S의 사이즈가 T의 사이즈가 같아질때까지 반복한다.