[C++] 12904 - A와 B

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

12904번: A와 B

 

처음 S를 T로 바꿀 수 있는지 BFS로 시도했다가 메모리 초과가 발생해서 생각을 해보니 최종 문자열에서 끝에 붙어있는 문자열에 맞는 규칙대로 줄여가다보면 T를 S로 바꿀 수 있지 않을까 생각을 하게 되서 짰다

 

T의 마지막이 A일 경우 1개만 줄이고 T의 마지막이 B일 경우에는 1개를 줄이고 문자열을 뒤집어주었다.

이 과정을 반복해서 S와 T의 길이가 같아졌을 때 비교를 해서 같으면 1, 아니면 0을 반환하게 했다.

 

 

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;

string reverse(string p)
{
	string res = "";

	for(int i = p.length()-1; i >= 0; --i)
		res += p[i];

	return res;
}

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL); 

	int blen, flen;

	string base;
	string last;
	cin >> base;
	cin >> last;

	blen = base.length();
	flen = last.length();

	while(blen < flen)
	{
		if(last[flen-1] == 'A')
			last = last.substr(0, flen-1);
		else
			last = reverse(last.substr(0, flen-1));

		flen-=1;
	}

	if(!base.compare(last))
		cout << "1" << endl;
	else
		cout << "0" << endl;

	return 0;
}