[백준] A와 B 12904번 C++ 풀이

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

12904번: A와 B

 

전체코드

#include <iostream>
#include <algorithm>
using namespace std;
string S, T;
int main(void)
{
	cin >> S >> T;
	while (S.length() < T.length())
	{
		if (T[T.length() - 1] == 'A')
			T.erase(T.length() - 1);
		else
		{
			T.erase(T.length() - 1);
			reverse(T.begin(), T.end());
		}
	}
	if (T == S)
		cout << "1";
	else
		cout << "0";

}

S를 T로 만드는 방법을 브루트포스,DFS,BFS등 방법으로 한다면 시간초과가 난다고 한다!?!

한 자리에 A,B 2개가 올 수 있는데 문자열 길이가 1000이라면 2의 1000승이다.

시간초과가 날것이다.

 

그래서 T를 S로 만드는 방법을 쓰자.

S를 T로 만드는 방법을 거꾸로 한다면 길이만큼 N번 반복하면 끝이다.

 

S->T의 연산을 거꾸로 한다면

1. 문자열의 뒤에 A를 추가한다 <-> 1. 문자열 뒤가 A라면 제거

2. 문자열을 뒤집고 뒤에 B를 추가한다. <-> 2. B를 제거하고 문자열을 뒤집는다.

 

여기서 문자열을 뒤집는다는게

A를 B로 B를 A로 바꾸는것이 아닌 그냥 ABBA 는 ABBA로 그냥 역순을 뜻하는거 였다...