백준 12919번 A와 B 2 문제풀이(C++)

백준 12919번 A와 B 2

아이디어

문제

• 문자열의 뒤에 A를 추가한다.
• 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

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

S -> T를 만들 수 있는지 구하는 문제

대충 생각해봐도 S -> T로 만들기 위한 시간 복잡도가
(연산 개수 : 2개)의 (T의 길이 : 50) 제곱정도 되는것 같다 ==> 시간초과

그럼 반대로 T -> S를 만드는 시간 복잡도를 생각해보자

위의 두 조건을 만족하기 위해
문자열의 맨 뒤가 A일 때
맨 앞이 B일 때만 재귀를 진행하면 된다

정답 코드

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
void ab(const string &str, const string& s)
{
	if (s.length() < str.length())return;
	string tmp = s;
	if (str == s)
	{
		cout << 1 << '\n';
		exit(0);
	}
	if (s[0] == 'B')
	{
		reverse(tmp.begin(), tmp.end());
		tmp.pop_back();
		ab(str, tmp);
	}
	if (s[s.length() - 1] == 'A')	
	{
		tmp = s;
		tmp.pop_back();
		ab(str, tmp);
	}
}
int main() {
	FAST_IO;
	string str, str2; cin >> str >> str2;
	ab(str, str2);
	cout << 0 << '\n';
	return 0;
}