문제 출처

1. 문제설명

  • 두 문자열 S, T가 주어진다.
  • S를 T로 바꾸는 게임이다.
    • 문자열의 뒤에 A를 추가한다.
    • 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
  • 바꿀 수 있다면 1 없으면 0 출력



2. 알고리즘 설계

  • 문제에는 S를 T로 바꾸라고 되어 있지만,
  • S를 T로 만드는 경우의 수는 매우 많다
  • T를 S로 바꿀 수 있는지? 확인하면 된다.



3. 로직

  • 문자열의 뒤에 A를 추가한다.
    • ==> 문자열의 뒤에 A를 제거한다.
  • 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.
    • ==> 문자열을 뒤집고 뒤에 B를 제거한다.


4. 전체 코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

void DFS(const string S, const string T) 
{
	if (S == T) {
		cout << 1;
		exit(0);
	}
	if (S.size() > T.size())
		return;
	
	if (T[T.size() - 1] == 'A') {
		string temp = T;
		temp.erase(temp.size() - 1);
		DFS(S, temp);
	}
	if (T[0] == 'B') {
		string temp = T;
		reverse(temp.begin(), temp.end());
		temp.erase(temp.size() - 1);
		DFS(S, temp);
	}
}

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

	string S, T;
	cin >> S >> T;

	DFS(S, T);

	cout << 0;
	return 0;
}


5. 소감

  • 처음에 S를 T로 바꾸는 모든 경우로 접근
    • 당연히 시간초과…
  • 문제를 풀 때 연산량이 적은 방향으로 해결해야겠다.
  • exit(0)을 사용하면 리턴값을 체크하지 않아도 된다.
    • 이거 안쓰면, main에서 0인지 1인지 추가로 확인해줘야 함.