BOJ_12886 : 돌 그룹

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다.

강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다.

크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

A, B, C가 주어졌을 때, 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 A, B, C가 주어진다. (1 ≤ A, B, C ≤ 500)

출력

돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력한다.

C++ 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#define MAX 500

using namespace std;
bool check[1505][1505];
int sum = 0;

void go(int a, int b) {
	check[a][b] = true;
	int arr[] = { a, b, sum - a - b };

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			if (arr[i] < arr[j]) {
				int temp[3] = { arr[i], arr[j] , sum - arr[i] -arr[j] };
				temp[0] += arr[i];
				temp[1] -= arr[i];
				if (!check[temp[0]][temp[1]]) {
					go(temp[0], temp[1]);
				}
			}
		}
	}
	return;
}

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

	int a, b, c;
	cin >> a >> b >> c;
	sum = a + b + c;

	//3 등분이 안되면 무조건 0
	if (sum % 3 != 0) {
		cout << 0 << '\n';
		return 0;
	}

	go(a, b);

	if (check[sum / 3][sum / 3]) {
		cout << 1 << '\n';
	}
	else
		cout << 0 << '\n';

	return 0;
}