백준 12904번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	골드 5

---

풀이

 밀린문제 풀이다. 이전번에 풀이한 12919번(https://codejin.tistory.com/282) 보다 덜 복잡한 문제이다. 저번 문제는 b를 추가한 후 문자열을 뒤집었기 때문에 문자열의 맨 앞과 맨 뒤를 고려해야하는 문제였지만. 이번 문제는 이보단 덜 복잡하다.

 

이 문제 역시 S->T로 가는 것은 경우의 수가 매우 많다. 문자열을 뒤집는 연산이 끼어있기 때문에, S에 적당히 연산을 한 S'가 T의 부분문자열이 아닐수도 있다. 부분문자열이더라도 여러 곳에서 등장할 수 있으며, 이때마다 어떤 연산을 고르는 것이 최적일지는 구분하기 힘들다.

 

 하지만 T->S로 바꿔보자 문자열 뒤에 A를 추가하는 연산을 거꾸로 하여 문자열 뒤의 A를 지우는 연산을 a작업, 문자열을 뒤집고 뒤에 B를 추가하는 연산을 거꾸로하여 문자열 뒤의 B를 지우고 문자열을 뒤집는 연산을 b작업이라고 하자. a작업과 b작업모두 문자를 맨 뒤에 추가하기 때문에 우리는 그리디하게 맨 뒤의 문자만 보고 a, b작업을 선택할 수 있다. 문자열 뒤에 A가 있다면 A를 추가하는 작업을 했다는 뜻이고, B가 있다면 문자열을 뒤집은 후 B를 추가했다고 명확히 판단할 수 있기 때문이다.

코드

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;

string s, t;

void sol() {
	while(s.length() < t.length()) {
		if (*t.rbegin() == 'A') {
			t.erase(t.end() - 1);
		}
		else {
			t.erase(t.end() - 1);
			reverse(ALL(t));
		}
	}
	cout << (s == t);
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> s >> t;
	sol();
}