백준 12904 - A와 B

문제링크

• 백준 12904

문제설명

• A와 B로만 이루어진 문자열 S와 T가 주어진다.
• 다음과 같은 2가지 규칙만을 이용하여 S를 T로 바꿀 수 있는지 알아내는 프로그램을 작성하라.
  • 문자열의 뒤에 A를 추가한다.
  • 문자열을 뒤집고 뒤에 B를 추가한다.

문제접근

• 처음에는 재귀호출을 통해 S -> T 를 만들어가도록 하였다. 즉, 완전탐색으로 풀려고 했었는데 시간초과에 걸렸다.
• 두번째는 그리디에서 힌트를 얻었고, 두가지 규칙을 살펴본 후 T -> S 로 한가지 루트를 통해서 탐색이 가능한 것을 알았다.
  • 만약 T의 마지막 문자가 A라면 1번 규칙에서 파생되었을 것이다.
  • 만약 T의 마지막 문자가 B라면 2번 규칙에서 파생되었을 것이다.
• 위 방법으로 T가 되기 이전의 글자를 만들어가면서 S와 길이가 같아졌을 때, 동일한 문자열인지의 여부로 정답을 출력한다.

구현 (그리디)

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


int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	string S, T;
	cin >> S >> T;
	
	string tmp = T;
	while (tmp.length() != S.length()) {
		if (tmp.back() == 'A') tmp.pop_back();
		else if (tmp.back() == 'B') {
			tmp.pop_back();
			reverse(tmp.begin(), tmp.end());
		}
	}
	if (tmp != S) printf("0\n");
	else printf("1\n");
}

구현 (재귀 - 시간초과)

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

string S, T;

void addA() {
	S += "A";
}

void removeA() {
	S.pop_back();
}

void addB() {
	reverse(S.begin(), S.end());
	S += "B";
}

void removeB() {
	S.pop_back();
	reverse(S.begin(), S.end());
}

bool makeStoT() {
	if (S.length() == T.length()) {
		if (S == T) return true;
		else return false;
	}

	bool ret = false;
	for (int i = 0; i < 2; i++) {
		if (i == 0) {
			addA();
			ret = ret | makeStoT();
			if (ret) return true;
			removeA();
		}
		else {
			addB();
			ret = ret | makeStoT();
			if (ret) return true;
			removeB();
		}
	}
	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	cin >> S >> T;
	int ans = (int)makeStoT();
	printf("%d\n", ans);
	return 0;
}