[BFS] 돌 그룹

예제 입력 1

10 15 35

예제 출력 1

1

예제 입력 2

1 1 2

예제 출력 2

0

 

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

12886번: 돌 그룹

- 시간 복잡도 + 공간 복잡도를 줄이기 위해 A, B만 저장하고 C는 처음에 A+B+C를 sum에 저장해두고 sum - B - A로 구한다. 

- A + B + C가 3으로 나누어 떨어지지 않는다면 풀 수 없으므로 0을 출력한다.

#include <stdio.h>

const int MAX_COUNT = 1500;

int A, B, C;
int sum;
bool used[MAX_COUNT][MAX_COUNT];

void swap(int& A, int& B)
{
	int temp = A;
	A = B;
	B = temp;
}

bool go(int A, int B)
{
	int numbers[] = { A, B, sum - A - B };
	
	used[A][B] = true;
	
	if (numbers[0] == numbers[1] && numbers[1] == numbers[2])
	{
		return 1;
	}

	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			if (numbers[i] < numbers[j])
			{
				int a = numbers[i] * 2;
				int b = numbers[j] - numbers[i];

				if (!used[a][b])
				{
					if (go(a, b) == 1) return 1;
				}
			}
		}
	}

	return 0;
}

int main(void)
{
	scanf("%d %d %d", &A, &B, &C);

	sum = A + B + C;

	if (sum % 3 != 0)
		printf("0\n");
	else
		printf("%d\n", go(A, B));

	return 0;
}