문제 소개 📌

문제 링크 📢

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

문제 풀이 📝

처음 봤을 때 드는 생각인 S에서 T를 만드는 방식은 경우의 수가 너무 다양해 접근하기 힘들다. 따라서 역방향인 T에서 S를 만드는 방식을 선택할 것이다.

필자는 C++에서 제공하는 문자열 함수와 재귀를 통한 완전 탐색으로 AC를 받았다.

T로부터 시작해 첫 번째 문자가 A일 때와 B일 때를 나누어 조건 처리를 해주고 완전 탐색을 하여 만약 T가 S가 될 수 없다면 0을 출력하였다.

코드

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

using namespace std;

string S, T;
bool flag = false;
string Recursion(string str)
{
	if (str.size() == S.size() || flag) // S와 길이가 같아졌거나 이미 그 문자열을 만들 수 있다면
	{
		if (str == S) 
			flag = true;
		return str;
	}
	if (str.size() > 0)
	{
		if (str[0] == 'A') // 첫 번째 문자가 A인 경우
		{
			if (str.back() == 'A')
			{
				str.pop_back();
				Recursion(str);
				str.push_back('A');
			}
		}
		else // 첫 번째 문자가 B인 경우
		{
			string tmp = str;
			reverse(tmp.begin(), tmp.end());
			str = tmp;

			str.pop_back();
			Recursion(str);

			reverse(tmp.begin(), tmp.end());
			str = tmp;
			if (str.back() == 'A') // 마지막 문자가 A인 경우
			{				
				str.pop_back();
				Recursion(str);
				str.push_back('A');
			}			
		}
	}
	return str;
}
int main()
{
	cin >> S >> T;
	Recursion(T);
	cout << flag;
	return 0;
}