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을 출력한다.

예제 입력 1

10 15 35

예제 출력 1

1

예제 입력 2

1 1 2

예제 출력 2

0

풀이

1. 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다
2. 크기가 같지 않은 두 그룹을 고른다.
3. 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다
4. X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.

목표: 강호가 돌을 같은 개수로 만들 수 있으면 1을, 아니면 0을 출력하는 프로그램을 작성하시오.

여기서 파악해야할 점은
X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
이부분이다.
결국 Y에서 X개를 X에다가 넘겨주기때문에 ABC의 합은 변하지 않는다.

import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static int sum = 0;
    public static boolean[][] check = new boolean[1501][1501];
    public static void go(int x, int y) {
        if (check[x][y]) return;
        check[x][y] = true;
        int[] a = {x, y, sum-x-y};
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (a[i] < a[j]) {
                    int[] b = {x, y, sum-x-y};
                    b[i] += a[i];
                    b[j] -= a[i];
                    go(b[0], b[1]);
                }
            }
        }

    }
	public static void main(String[] args) throws NumberFormatException, IOException {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int z = sc.nextInt();
		sum = x + y + z;
		if (sum % 3 != 0) { //3개의 그룹에 같은 값으로 나눠야하는데 똑같이 나눌려면 3으로 나눠떨어져야한ㄷ다.
			System.out.println(0);
			System.exit(0);
		}
		//sum에서 구한 두개를 빼면 나머지 숫자는 자련스럽게 알게되기때문에 2개의 정점만 필요
		 go(x, y);
		 //똑같이 나눴을 경우 배열에 가서 방문했는지만 알면됨
		 if (check[sum/3][sum/3]) {
	            System.out.println(1);
	        } else {
	            System.out.println(0);
	        }
	}
}