[백준] 12904-A와 B(C++)

문제링크:www.acmicpc.net/problem/12904

12904번: A와 B

 

(1 ≤ S의 길이 ≤ 999, 2 ≤ T의 길이 ≤ 1000, S의 길이 < T의 길이)

문자열의 범위가 위와 같으므로 재귀함수를 사용해 구현하면 시간 초과입니다.

 

S를 통해서 T를 만드는데 이때 T를 통해서 S를 유추하면 더욱 쉽다는 것을 아는지 모르는지에 따라서 난이도가 크게 달라지는 문제입니다.

 

T에서 두가지 규칙에 의해서 S문자열의 길이와 같아지게 될때 까지 반복하면 S를 통해서 T를 만들 수 있는지 여부가 결정되기 때문입니다.

 

구현자체의 난이도는 하,  문제 해결 아이디어가 중상..

 

아래는 정답코드입니다. 코드로 보면 충분히 이해가 되실겁니다.

 

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


string s, t;
bool result = 0;


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> s;
	cin >> t;


	while (1) {

		if (s.size() == t.size()) {
			if (s == t)
				result = 1;
			break;
		}
		
		if (t[t.size() - 1] == 'A')
			t.pop_back();
		else {
			t.pop_back();
			reverse(t.begin(), t.end());
		}
	}

	cout << result << endl;
}