[백준] #12904 A와 B

12904번: A와 B (acmicpc.net)

12904번: A와 B

아무리 생각해도 브루트포스로 풀면 시간초과가 나올거 같아 생각을 하던 중, S에서 T를 만들지 말고 T에서 S를 만드는 방법으로 생각하니 금방 풀렸다.

---

• 풀이

T에서 S로 만드는 알고리즘으로 바꾸어 생각해보자.

그렇다면 적용할 수 있는 연산은 T의 마지막 글자에 따라 무조건 하나로 정해지게 된다.

case 1. T의 마지막 글자가 A인 경우 : pop_back()
case 2. T의 마지막 글자가 B인 경우 : pop_back() 후, reverse로 거꾸로 정렬

이후 두 문자의 길이에 따라 적절히 반복문 제어 후 출력

T의 마지막 글자에 따라 명확한 규칙성이 생기기 때문에 훨씬 더 쉽게 구현할 수 있다.

---

• 구현

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    string S, T;
    cin >> S >> T;

    bool flag = false;
    int lenS = S.length(), lenT = T.length();

    while (lenS <= lenT) {
        if (S == T) {
            flag = true;
            break;
        }
        if (T.back() == 'A') T.pop_back();
        else {
            T.pop_back();
            reverse(T.begin(), T.end());     
        }
        lenS = S.length();
        lenT = T.length();
    }

    flag ? cout << 1 : cout << 0;

    return 0;
}

---