[그리디 알고리즘] A와 B

예제 입력 1

B

ABBA

예제 출력 1

1

예제 입력 2

AB

ABB

예제 출력 2

0

 

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

12904번: A와 B

- BFS로 풀려면, 최악의 경우 S의 글자 수가 최소 1, T의 글자 수가 최대 1000이기 때문에 2^999라는 시간 복잡도가 나와서 풀 수 없다.

- 따라서, 다른 방법을 이용해야만 하는데, 각 연산이 A가 제일 뒤에 추가되거나 B가 제일 뒤에 추가되는 경우 밖에 없다는 점을 이용해, 역으로 T를 S로 바꾸면서 문제를 풀어본다.

- T의 맨 마지막 글자가 A이면 연산 #1을 쓴 것일 수 밖에 없고, 맨 마지막 글자가 B이면 연산 #2를 쓴 것일 수 밖에 없다.

- 따라서 T의 맨 마지막 글자가 A이면 그냥 맨 마지막 글자를 빼고, B이면 맨 마지막 글자를 빼고 글자를 모두 뒤집어가면서, S와 T의 글자수가 같아질 때까지 반복한다. 마지막으로 비교해서 같은 글자이면 가능한 것이고, 아니면 불가능한 것이다.

#include <stdio.h>

constexpr int MAX_SIZE = 1001;

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

	vector() {}

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

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

			i++;
			j--;
		}
	}

	void removeLast()
	{
		size--;
		data[size] = '\0';
	}

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

		size = i;
	}
};

int main(void)
{
	vector S;
	vector T;

	scanf("%s", S.data);
	S.updateSize();

	scanf("\n%s", T.data);
	T.updateSize();

	while (S.size != T.size)
	{
		if (T.data[T.size - 1] == 'A')
		{
			T.removeLast();
		}
		else
		{
			T.removeLast();
			T.reverse();
		}
	}

	int i = 0;
	while (S.data[i] != '\0')
	{
		if (S.data[i] != T.data[i])
		{
			printf("0\n");
			return 0;
		}

		i++;
	}

	printf("1\n");

	return 0;
}