BOJ) 12904 - A와 B

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

12904번: A와 B

처음  풀이할 땐 S에서 T의 길이까지 만들 수 있는  모든 문자열의 경우를 구해보았습니다.

나름 Set을 사용해서 중복체크도 했지만.. 메모리 초과

 

새로운 풀이에서는 반대로 접근하여 T에서 S를 만들 수 있는지 체크하였습니다.

 

문제에 주어진 S -> T 연산을 거꾸로 적용합니다.

- 문자열의 뒤에 A를  추가한다 : 문자열 뒤에 A를 제거한다.

- 문자열을 뒤집고  뒤에 B를 추가한다 : B를 제거하고 문자열을 뒤집는다

 

T의 길이가 S의 길이와 같아질 때까지 위 연산을 적용한 결과가 S와 같다면 S -> T가 가능한 경우입니다.

---

C++ 소스 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s,t;
    cin >> s >> t;
    while(t.length()> s.length()){
        if (t.back()=='A') t.pop_back();
        else {
            t.pop_back();
            reverse(t.begin(),t.end());
        }
    }
    if (s == t) cout << 1 << '\n';
    else cout << 0 << '\n';
    return 0;
}