❓문제 설명

문제 : 백준 12904 A와 B
난이도 : 골드 5

문제 요약

• A와 B로만 이루어진 영어 단어 S, T가 주어집니다.
• S를 T로 바꾸는 게임을 진행하는데 두 가지 연산만 가능합니다.
  1. 문자열의 뒤에 A를 추가한다.
  2. 문자열을 뒤집고 뒤에 B를 추가한다.
• 이때 S를 T로 만들 수 있으면 1, 만들 수 없으면 0을 출력하면 됩니다.

저번에 다나가 발표한 A와 B 2 문제와 매우 비슷합니다.

다른 점으로는 2번째 연산이 문자열의 뒤에 B를 먼저 추가하고 문자열을 뒤집습니다. 추가로 S와 T의 범위가 A와B 2 문제 보다 A와B가 더 크다는 점이 다릅니다.

A와B 2는 S,T 범위가 작아서 완전탐색을 이용해서 풀 수 있지만
A와B 문제는 완전탐색으로 풀게되면 시간초과가 발생합니다.

🎯문제 해결 방법

완전 처음 문제를 봤다면 바로 A를 B로 만들 수 있는지 A를 가지고 어떻게 해보려고 했을 것 같습니다ㅋㅋ

A와 B 2 발표를 들었기에 B가 A가 될 수 있는가를 바로 확인했습니다.

이 문제는 그리디하게 문제를 풀 수 있습니다.

cin >> s;
cin >> t;
func(s,t);

두 문자열을 입력받고 func(s,t)를 실행합니다.
바로 func 함수를 주석으로 살펴보겠습니다.

void func(string a, string b){
	int az = a.size(); // a의 길이
	int bz = b.size(); // b의 길이
	if(bz == a.size()){ // 지금까지 변형된 b의 길이와 a의 길이가 같을 때
		if(a == b){ // a와 b가 같아서 b가 a로 변할 수 있음을 확인하면
			cout << 1; 
		}else cout << 0;
		return;
	}
	
	if(b[bz-1] == 'A'){ // b의 마지막이 A라면
		func(a, b.substr(0, bz-1)); // b에서 A를 제거한 뒤 func 함수를 호출합니다.
	}else if(b[bz-1] == 'B'){ // b의 마지막이 B라면
		string tmp = b.substr(0, bz-1); // b에서 B를 제거한 뒤 tmp에 담습니다.
		reverse(tmp.begin(), tmp.end()); // B를 제거한 tmp를 reverse 함수를 통해 뒤집습니다.
		func(a, tmp); // B를 제거하고 문자열을 뒤집어 func 함수를 호출합니다.
	}
	return;
}

코드를 그림으로 살펴보게 되면

ABBA -> ABB -> BA -> B

그리디하게 다음 비교 문자를 선택해서 진행함을 알 수 있습니다.

💻전체 코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
string s,t;

void func(string a, string b){
	int az = a.size();
	int bz = b.size();
	if(bz == a.size()){
		if(a == b){
			cout << 1;
		}else cout << 0;
		return;
	}
	
	if(b[bz-1] == 'A'){
		func(a, b.substr(0, bz-1));
	}else if(b[bz-1] == 'B'){
		string tmp = b.substr(0, bz-1);
		reverse(tmp.begin(), tmp.end());
		func(a, tmp);
	}
	return;
}

int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> s;
	cin >> t;
	func(s,t);
	return 0;
}