[그리디 알고리즘/Brute Force] A와 B 2

예제 입력 1

A

BABA

예제 출력 1

1

예제 입력 2

BAAAAABAA

BAABAAAAAB

예제 출력 2

1

예제 입력 3

A

ABBA

예제 출력 3

0

 

- 거꾸로 T에서 S를 만들어 가면서 가능한지 풀어본다.

- 직접 무작정 다 돌려보면 시간복잡도가 2^49이기 때문에 불가능하다.

- 현재 T의 마지막 글자가 A이면 반드시 A연산을 이용해야하며, 첫글자가 B이면 B연산을 이용했음을 알 수 있다. 그런데 첫글자가 B이고 마지막이 A이면 A와 B연산 모두 가능한데, 재귀로 구현하여 두 가지 모두 고려한다.

// A --- A : A연산 
// A --- B : 불가능 
// B --- A : A연산과 B연산 모두 가능 
// B --- B : B연산 

 

- 두 방법으로 나누어지는 경우가 총 N-1번 있다.

- 모든 단계에서 문자열이 1씩 감소하므로 총 가능한 (S, T)쌍은 N^2이다.

- 문자열 연산은 N이므로 총 시간 복잡도는 N^3

 

#include <stdio.h>

const int MAX_SIZE = 51;

class vector
{
public:
	char data[MAX_SIZE];
	int size;

	vector() { size = 0; }

	void push(int item)
	{
		data[size] = item;
		size++;
	}

	void updateSize()
	{
		int s = 0;
		while (data[s] != '\0') s++;

		size = s;
	}

	bool operator==(vector other)
	{
		if (size != other.size) return false;
		if (size == 0) return true;

		int i = 0;

		while (i < size)
		{
			if (data[i] != other.data[i]) 
				return false;
			i++;
		}

		return true;
	}

	vector clone()
	{
		vector result;
		result.size = size;

		for (register int i = 0; i < size; i++)
			result.data[i] = data[i];

		return result;
	}

	vector* pop()
	{
		size--;
		data[size] = '\0';

		return this;
	}

	vector* reverse()
	{
		int i = 0;
		int j = size-1;

		while (i < j)
		{
			char temp = data[i];
			data[i] = data[j];
			data[j] = temp;

			i++;
			j--;
		}

		return this;
	}
};

vector S;
vector T;

bool convert(vector s, vector t)
{
	if (s == t) 
		return true;

	// A --- A : A연산
	// A --- B : 불가능
	// B --- A : A연산과 B연산 모두 가능
	// B --- B : B연산

	if (t.data[t.size - 1] == 'A')
	{
		if (convert(s, *(t.clone().pop())))
		{
			return true;
		}
	}
	if (t.data[0] == 'B')
	{
		if (convert(s, *((t.reverse())->pop())))
		{
			return true;
		}
	}

	return false;
}

int main(void)
{
	scanf("%s", S.data);
	S.updateSize();
	scanf("\n%s", T.data);
	T.updateSize();

	if (convert(S, T)) printf("1\n");
	else printf("0\n");

	return 0;
}