[C++] BJO 12919 : A와 B 2

문제

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

 

풀이

1. S로 T를 만드는 방향으로 탐색을 하는 것이 아니라, T로 S를 만드는 방향으로 탐색을 한다.

2 . T의 마지막 문자가  A인 경우 마지막 문자 제거 후 재귀 호출.

3 . T의 첫 분자가 B인 경우 뒤집은 후 마지막 문자 B 제거 후 재취 호출.

4. 만약 S의 길이보다 T의 길이가 짧아지거나 두 문자열이 같아질 경우 재귀 종료.

 

이렇게 구현하면 된다.

S로 T를 만드는 방향으로 탐색을 할 경우, 사용한 방식에 따라 다를 수 있겠지만 높은 확률로 시간초과가 발생할 수 있다.

왜냐하면 문제에서는 2 연산 중 하나만 수행할 수 있다고 하지만,  S에 어떤 연산이 일어났는지를 알 수 없기 때문에 두 연산을 모두 검사해야만 하고, 따라서 최악의 경우 2^49 정도의 높은 복잡도를 가지게 될 수 있다.

 

하지만 T로 S를 만드는 방향으로 탐색을 하면 적어도 어떤 연산이 이루어졌는가를 알아내어 발생했을 것이라 예상되는 연산만을 처리할 수 있다.

T의 마지막 문자가 A라면 1번 연산이 발생한 것이고 T의 첫 문자가 B라면 2번 연산이 발생한 것이다. (반대의 경우는 발생하지 않은 것이다.)

물론 마지막 문자가 A 이면서 첫 문자가 B인 경우도 있다. 이때 어떤 연산이 먼저 일어났는지는 알 수 없기 때문에 각 조건문마다 각각 재귀 호출을 해주어야 한다. (즉 각각 if 문으로 처리해주어야 하고, if-els if 이용하면 틀리는 경우 발생한다.)

 

 

코드

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

string S, T;
bool canConvert = false;

void solve(string T) {
    if (T == S) { // 목표 문자열 S를 만들었다면 성공
        canConvert = true;
        return;
    }
    if (T.length() <= S.length()) return; // 더 이상 줄일 수 없으면 종료

    if (T.back() == 'A') { // 마지막이 'A'면 제거하는 연산 수행
        solve(T.substr(0, T.size() - 1));
    }
    if (T.front() == 'B') { // 첫 문자가 'B'면 뒤집고 'B' 제거
        reverse(T.begin(), T.end());
        solve(T.substr(0, T.size() - 1));
    }
}

int main() {
    cin >> S >> T;
    solve(T);
    cout << (canConvert ? "1\n" : "0\n");
    return 0;
}