백준 12904 A와 B C++

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

12904번: A와 B

A,B로만 이루어진 문자열이 주어졌을 때

1. 문자열 뒤에 A 붙이기

2. 뒤집고 B 붙이기 

2가지 연산이 가능합니다.

 

이 때 주어진 문자열 S로 T를 만들 수 있는지 확인하는 문제입니다. 

 

문제를 반대로 생각하면, T의 마지막이 A이면 A를 떼버리고, 마지막이 B이면 떼고 뒤집으면 됩니다.

그리고 S와 비교하여 같은지 아닌지 판단하면 됩니다.

 

코드는 다음과 같습니다.

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

string S, T;

void init()
{
	cin >> S >> T;
}
// T를 기준으로 마지막이 A면 A 빼주고
// B면 빼주고 뒤집기 반복
// S 나오면 1, 아니면 0

int calculate(string str) {
	int len = str.size();
	if (str == S)
		return 1;
	else if (len == S.size() && str != S)
		return 0;
	else {
		if (str[len - 1] == 'A')
			return calculate(str.substr(0, len - 1));
		else {
			string substr = str.substr(0, len - 1);
			string reversestr(substr.rbegin(), substr.rend());
			return calculate(reversestr);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	init();
	cout << calculate(T);
}