BOJ 12904 - A와 B

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

두 문자열을 입력받고

주어진 두가지의 연산을 사용해서

첫번째 문자열을 두번째 문자열로 바꿀수 있는지를 출력하시오.
(S->T)

Solution

1. 문자열 뒤에 A를 추가한다.
2. 문자열을 뒤집은 다음 B를 추가한다.

-> 연산으로 붙여주는 A와 B는 항상 문자열 '뒤'에 붙는다.
그리고 A와 B를 붙여주는 연산은 각각 하나씩 뿐이다.

이 특징을 사용하여서 S에서 T를 만드는것이 아닌 반대로 T에서 S를 만들수 있는지 검사해본다.

T가 A로 끝났다면 A를 없애주고, T가 B로 끝났다면 B를 없앤다음에 문자열을 뒤집어준다.

Code

#include <bits/stdc++.h>
using namespace std;

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

    string s1, s2;
    cin >> s1 >> s2;
    int len = s2.length() - 1;

    for (int i = len; i >= 0; i--) {
        if (s1 == s2) { 
            cout << 1 << '\n';
            return 0;
        }

        if (s1.length() > s2.length()) break;

        if (s2.back() == 'A') {
            s2.pop_back();
        }

        else if (s2.back() == 'B') {
            s2.pop_back();
            reverse(s2.begin(), s2.end());
        }
    }
    cout << 0 << '\n';

    return 0;
}

참고 : https://code.plus/course/43 , 그리디 알고리즘(연습)