백준 12919 A와 B 2

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

#include <iostream>
#include <cmath>
#include <stack>
#include <algorithm>

using namespace std;

void solve(string s, string t){
    if (s == t) {
        cout << 1;
        exit(0);
    }
    if (s.size() > t.size()) {
        return;
    }

    if (t.back() == 'A') {
        string temp = t;
        temp.pop_back();
        solve(s, temp);
    }

    if (t.front() == 'B') {
        string temp = t;
        reverse(temp.begin(), temp.end());
        temp.pop_back();
        solve(s, temp);
    }


}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    string s1, s2;

    cin >> s1 >> s2;

    solve(s1, s2);

    cout << 0;


    return 0;
}

1. 문제

두 문자열이 주어진다. 이 처음 주어진 문자열에서 두 가지 연산을 통해 두 번째 문자열을 만드려고 한다. 해당 연산은 다음과 같다.

• 문자열의 뒤에 A 추가
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집기

해당 연산을 통해 문자열 변경이 가능한지 여부를 구하는 문제이다.

2. 풀이

첫번째 문자열(s)에서 두번째 문자열(t)로 간다고 생각해보면, s의 길이는 최소 1, t의 길이는 최대 50이므로 최대 연산 횟수가 2^49로, 2초 내에 연산이 불가능하다. 따라서 반대로 t에서 s로 가는 경우를 탐색해야 한다.

 두 가지 경우를 각각 생각해보자

  2-1 문자열의 뒤에 A 추가

이 경우 새 문자열 T의 맨 뒤의 문자는 A가 된다. 즉, t의 문자열의 마지막이 A일 경우, 역으로 연산할 수 있는 가능성이 생긴다.

  2-2 문자열의 뒤에 B를 추가하고 문자열을 뒤집기

이 경우 새 문자열의 맨 뒤가 B였다가, 뒤집는 연산을 통해 맨 앞의 문자가 B가 된다.

 

 위의 두 경우를 고려하여 함수를 만들면 다음과 같다.

void solve(string s, string t){
    if (s == t) {
        cout << 1;
        exit(0);
    }
    if (s.size() > t.size()) {
        return;
    }

    if (t.back() == 'A') {
        string temp = t;
        temp.pop_back();
        solve(s, temp);
    }

    if (t.front() == 'B') {
        string temp = t;
        reverse(temp.begin(), temp.end());
        temp.pop_back();
        solve(s, temp);
    }


}

 두 문자열이 같아지면 이를 출력하고 프로그램을 종료한다. 또, 문자열이 줄어드는 경우는 없으므로 s의 크기가 더 큰 경우에는 연산을 통해 문자열을 만들 수 없다.

 이 이후에는 위의 두 경우를 확인하는데, 재귀함수를 통해 두 가지 경우를 모두 확인할 수 있다. 함수를 빠져나가게 되면 문자열을 만들 수 없다는 0을 출력하면 정답을 구할 수 있다.