[BOJ/백준 12919][C++] A와 B 2

문제

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

백준 12919

 

문제 내용

문자열 s와 t를 입력받아 아래의 연산들을 수행했을 때 s가 t가 될 수 있는지를 구하면 된다.

- 문자열의 뒤에 A를 추가한다.
- 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

 

문제 풀이

이 문제를 s에서 t로 변환 가능한지로 풀이하면 안 된다.

s에서 위의 2가지 연산을 했을 때 t가 되는지 판단하는 것은, t의 길이가 50까지 가능하기 때문에 약 2^50가지의 경우를 체크해야 하기 때문이다. (실제로 이렇게 풀었더니 시간 초과가 발생함)

 

이 문제는 t에서 s로 변환 가능한지 체크해야 한다.

마지막 글자가 A인 경우와, 첫 글자가 B인 경우를 보며 되돌아오면 된다.

 

코드

t -> s 방식

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

string s, t;

void changeString(string tmp) {
    if (tmp == s) {
        cout << 1;
        exit(0);
    }

    if (tmp.size() <= s.size())
        return;

    if (tmp[tmp.size() - 1] == 'A') {
        string newTmp = tmp;
        newTmp.erase(newTmp.end() - 1);
        changeString(newTmp);
    }
    if (tmp[0] == 'B') {
        string newTmp = tmp;
        newTmp.erase(newTmp.begin());
        reverse(newTmp.begin(), newTmp.end());
        changeString(newTmp);
    }
}

int main() {
    cin >> s >> t;
    changeString(t);
    cout << "0";
    return 0;
}

 

시간 초과 코드

s -> t 방식

아래와 같이 재귀로 모든 경우를 체크하면 2^50이라 시간초과 발생
#include <algorithm>
#include <iostream>

using namespace std;

string before, after;

void changeString(string tmp) {
    if (tmp.size() == after.size()) {
        if (tmp == after) {
            cout << "1";
            exit(0);
        } else
            return;
    }

    changeString(tmp + "A");

    string reverseTmp = tmp + "B";
    reverse(reverseTmp.begin(), reverseTmp.end());
    changeString(reverseTmp);
}

int main() {
    cin >> before >> after;
    changeString(before);
    cout << "0";
    return 0;
}