백준 12904번 A와 B C++

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

 

처음에는 S에서 백트래킹을 해서 T로 가는 방법을 생각해봤는데 범위를 보니 무조건 시간초과가 날 것 같아서 다른 방법을 생각해 보았다.

 

T에서 S로 거꾸로 거슬러 올라가는 방법으로 문제를 해결하였다.

T의 맨 뒤가 A라면 그냥 A를 빼고

T의 맨 뒤가 B라면 B를 빼고 문자열을 뒤집어준다.

이걸 반복하다가 S와 길이가 같아졌을 때 S와 T가 일치하면 S로 T를 만들 수 있는 것이고, 일치하지 않는다면 만들 수 없는 것이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
		
	string s, t;
	cin >> s >> t;

	int ans = 0;
	while (true) {
		if (s.length() == t.length()) {
			if (s == t) {
				ans = 1;
			}
			break;
		}
		char c = t[t.length() - 1];
		t = t.substr(0, t.length() - 1);
		if (c == 'B') {
			reverse(t.begin(), t.end());
		}
	}
	cout << ans;
};