백준 Gold 5 A와 B

A와 B (백준 Gold 5)

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

처음에는 어떻게 풀지 몰라서 꽤나 고민하였다

고민한 부분

아무리 생각해도 A에 값을 추가하여도
백트래킹 문제에 가까워지며

• 뒤에 A를 추가
  
• 뒤집고 뒤에 B 추가
  

라는 조건이 있어도
그것만으로 ‘B’에 가까워지는지를 판별하기 어려웠다

그렇다고 정말로
각각의 조건을 전부 고려한 코드를 짜는 경우
최악의 경우 O(2^n)이 되며
목표인 b가 1000에 가까운 값이 들어올 수 있기에
그렇게 구현하더라도 시간초과가 발생할 것 같았다

생각의 전환

그렇기에 곰곰히 생각을 해본 결과
‘반대로 B를 A로 만드는 과정’은 어떨지에 대하여 생각해보았다

그렇다면 위의 조건들은

• 내 뒤에 A가 있다면 A 제거
  
• 내 뒤에 B가 있다면 B 제거 후 뒤집기
  

가 되며
이 둘이 ‘불가능’하다면
B는 A로 만들 수 없는 것

무척 그리디한 알고리즘이 되었지만
실제로 B를 A로 만든다는 것이
조건을 변형하면 충분히 판별이 가능하다고 생각하였고

위와는 다르게 이미 있는 B를
A에 맞게 변형해가면서, 조건에 맞지 않으면
바로 ‘포기’하면 되니

충분히 괜찮은 알고리즘이라 생각하였다

제출 코드

#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

bool canA(string& a, string& b)
{
	if (a == b)
		return true;

	if (a.size() == b.size())
		return false;

	if (b.back() == 'A')
	{
		string t = b;
		t.pop_back();
		if (canA(a, t))
			return true;
	}

	if (b.back() == 'B')
	{
		string t = b;
		t.pop_back();
		reverse(t.begin(), t.end());
		if (canA(a, t))
			return true;
	}

	return false;
}

int main()
{
	string a, b;
	cin >> a >> b;
	cout << canA(a, b) ? 1 : 0;

	return 0;
}

결과

처음에 #include을 안해주어 컴파일 에러
그 다음은 두 번째 'B'문단에서 t.pop_back()과
reverse를 엇갈려 써서 첫 예제에서 0이 나온걸 그대로 제출해버렸다

이후 수정하여 정답

발상의 전환이 중요한 문제였다