[BOJ]12919번: A와 B 2 (c++)

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

12919번: A와 B 2

 

그리디

#include <iostream>
#include <algorithm>

using namespace std;

// 첫번째 연산 원복하기
string rule_1(string str)
{
	str.pop_back();
	return str;
}

// 두번째 연산 원복하기
string rule_2(string str)
{
	reverse(str.begin(), str.end());
	str.pop_back();
	return str;
}

bool change(string from, const string &to)
{
	// 두 문자열이 동일하면 true반환
	if (from.compare(to) == 0)
	{
		return true;
	}
	// 규칙으로 만들어질수 없는 경우이거나, 두 문자열이 같지 않은데 길이가 서로 같으면 false 반환
	if (from.front() == 'A' && from.back() == 'B' || from.size() <= to.size())
	{
		return false;
	}

	// from의 맨 뒤가 'A'이고, 첫번째 연산을 원복한 문자열로 change재귀함수 돌린 결과가 true이면
	if (from.back() == 'A' && change(rule_1(from), to))
	{
		return true;
	}
	// from의 맨 앞이 'B'이고, 두번째 연산을 원복한 문자열로 change재귀함수 돌린 결과가 true이면
	if (from.front() == 'B' && change(rule_2(from), to))
	{
		return true;
	}
	
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	/*
		접근방식 : 두번째 문자열을 원복시켜서 첫번째 문자열로 만들수 있는지 확인하기
	*/
	string to, from;
	cin >> to >> from;

	cout << change(from, to);

	return 0;
}

 

 

좀 가지를 많이 친 완전탐색이라고 볼수도 있을 것 같다.

 

첫째 줄에 S가 둘째 줄에 T가 주어진다. (1 ≤ S의 길이 ≤ 49, 2 ≤ T의 길이 ≤ 50, S의 길이 < T의 길이)

문자열을 바꿀 때는 다음과 같은 두 가지 연산만 가능하다.
1. 문자열의 뒤에 A를 추가한다.
2. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다.

S를 T로 바꿀 수 있으면 1을 없으면 0을 출력한다.

 

문제는 첫번째 문자열 -> 두번째 문자열 바꿀수 있는가를 확인하라고 되어있지만

위 코드는 "두번째 문자열 -> 첫번째 문자열로 원복할 수 있는가"를 구현하였다.

왜냐면 규칙을 원복했을 때 나올수 없는 결과 찾기가 더 간편하기 때문이다.

 

 

1번 규칙의 결과는 ○○○○○A

2번 규칙의 결과는 B○○○○○ 가 되며,

A○○○○B 처럼 A로 시작하고 B로 끝나는 경우는 존재할수 없다!

(첫번째 문자열이 처음부터 그렇게 주어지지 않았다면..)

// 다음 재귀함수의 종료조건은 위의 내용을 반영한 것이다.

// 두 문자열이 동일하면 true반환
if (from.compare(to) == 0)
{
	return true;
}
// 규칙으로 만들어질수 없는 경우이거나, 두 문자열이 같지 않은데 길이가 서로 같으면 false 반환
if (from.front() == 'A' && from.back() == 'B' || from.size() <= to.size())
{
	return false;
}

 

 

따라서 뒤에 A있으면 A떼고, 앞에 B있으면 B떼고 하는 식으로 두번째 문자열을 원복시켜나간다.

// from의 맨 뒤가 'A'이고, 첫번째 연산을 원복한 문자열로 change재귀함수 돌린 결과가 true이면
if (from.back() == 'A' && change(rule_1(from), to))
{
	return true;
}
// from의 맨 앞이 'B'이고, 두번째 연산을 원복한 문자열로 change재귀함수 돌린 결과가 true이면
if (from.front() == 'B' && change(rule_2(from), to))
{
	return true;
}


// 첫번째 문자열과 같아질때까지! 또는 떼고봤더니 불가능한 경우가 땃 하고 나올때까지!
// 재귀함수를 호출하여 위 연산을 반복한다