A와 B C++ - 백준 12904

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

그리디 문제.

일단 그리디 문제의 틀에 박혀있지 않기

처음에는 "뭔가 그리디적인 방법이 있다."

"S->T로 갈때에 결국 T의 A의 개수와 S의 A개수가 같아야 하고"

"T의 B개수와 S의 B 개수가 같아야 한다!"

라면서 깊이 생각하지 않고 접근했던 것 같다.

평소에 깊게 생각하는 습관을 들여야겠다.

문제 접근

더 본질적으로 생각해보자.

사실상 T로 오는 S는 항상 정해져있다.

문제에 있는 A,B를 추가할 때에는 항상 뒤쪽에 추가한다.

어떤 문자열의 맨 뒤 문자가 B일때는

행동 2를 한 결과이고, 어떤 문자열의 맨 뒤 문자가 A일때는

행동 1을 한 결과이다.

따라서 T에서 행동의 역과정을 하다보면 길이가 S와 같은 때가 온다.

그때 S와 비교해 S가 적절한 문자열인지 확인해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	string s,t; cin >> s >> t; int sl=s.length(); int tl=t.length();
	bool st=true;
	while(tl!=sl){
		if(st){
			if(t[tl-1]=='B') st=false;
			t.erase(tl-1,1);
		}
		else{
			if(t[0]=='B') st=true;
			t.erase(0,1);
		}
		tl--;		
	}
	if(st) for(int i=0;i<tl;i++){if(t[i]!=s[i]){cout << 0; return 0;}}
	else for(int i=0;i<tl;i++){if(t[i]!=s[sl-(i+1)]){cout << 0; return 0;}}
	cout << 1;
}