백준 12904번 A와 B C++

처음 푼 방식

(틀린 코드)

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

string s, t, reverseT = "";
bool isReverse = false;

bool AB(string str) {
	if (str.length() == t.length()) {
		if (isReverse) {
			if (str == reverseT)
				return true;
		}
		else if (str == t)
			return true;

		return false;
	}

	if (isReverse) {
		if (AB("A" + str))
			return true;
		
		isReverse = !isReverse;
		if (AB(str + "B"))
			return true;
		isReverse = !isReverse;
	}
	else {
		if (AB(str + "A"))
			return true;

		isReverse = !isReverse;
		if (AB("B" + str))
			return true;
		isReverse = !isReverse;
	}

	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> s >> t;

	for (int i = t.length() - 1; i >= 0; --i) 
		reverseT += t[i];

	if (AB(s))
		cout << "1";
	else
		cout << "0";
	

	return 0;
}

 

되는대로 재귀로 풀어보자! 해서 푼 코드

 

당연히 시간초과가 나왔다

 

 

도움을 받은 질문글

https://www.acmicpc.net/board/view/83783

 

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

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string s, t;
	cin >> s >> t;

	while (t.length() > s.length()) {
		if (t.back() == 'A')
			t.pop_back();
		else if (t.back() == 'B') {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}

	if (t == s)
		cout << "1";
	else
		cout << "0";

	return 0;
}

 

s -> t 로 생각하지 말고

t -> s 로 생각하면 쉽다

 

t의 마지막 문자가 B일 경우,

t를 만들 때, 무조건 뒤집고 B를 추가 했을 테니  마지막 문자 B를 지우고 뒤집으면 그 문자를 만들기 한 단계전 문자열로 되돌릴 수 있다.

반대로 마지막 문자가 A일 경우는 A를 빼주기만 하면 한 단계 전 문자열로 되돌릴 수 있다.

 

t와 s의 길이가 같아졌을 때, while문을 빠져나오고

t와 s를 비교하면 답을 알 수 있다.

 

발상의 전환이 필요했던 문제

 

 

 

 

 

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