[BOJ/C++] A와 B 2(12919번)

1. 개요

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

12919번: A와 B 2

1-1. 설명

A와 B로 이루어진 영단어를 통해 간단한 게임을 만들었다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀때는 다음과 같은 두가지 연산만 가능하다.

 - 문자열 뒤에 A 추가

 - 문자열 뒤에 B를 추가 후 문자열을 뒤집음

주어진 조건을 이용해 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성한다. 

1-2. 제한 사항

 - 첫 줄에 S, 둘째 줄에 T가 주어짐

 - S는 1 이상 49 이하, T는 2 이상 50 이하이며 S 길이는 T 길이보다 적음

2. 구현

2-1. 풀이

우선 S에서 T를 만든다는 생각이 아닌, T에서 S로 만들어 보자는 생각을 하였다. while 문으로 조건을 따라 구현하였으나, 모든 조건에 대해서 검사하기 위해 재귀 방식으로 변경하였다. 

2-2. 코드 

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

int result = 0;
void recursive(string input, string str);

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

    string input, output;
    cin >> input >> output;

    recursive(input, output);

    cout << result << "\n";

    return 0;
}

void recursive(string input, string str) {
    if (input == str) result = 1;
    if (input.size() >= str.size()) return;

    if (str[str.size() - 1] == 'A') { // 1. 문자열 뒤에 A 추가
        recursive(input, str.substr(0, str.size() - 1));
    }
    if (str[0] == 'B') { // 2. 문자열 뒤에 B 추가 + reverse
        reverse(str.begin(), str.end());
        recursive(input, str.substr(0, str.size() - 1));
    }
}