문제

돌 그룹
시간 제한 메모리 제한
2 초 512 MB
문제
오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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을 출력한다.

풀이

시간 복잡도

• 그룹 하나당 가질수 있는 경우수는 A+B+C
• 전체 돌 그룹 3개가 모두 다르다면 A != B != C 3가지 경우를 모두 탐색한다.
• 만약 3가지 경우를 모두 본다면 N^3 이되서 1500^3 이 된다.
• 메모리의 경우 1500^3 이 넘는다.
• 여기서 총합은 변하지 않는다 라는 사실을 활용하면 N^2 로 줄일 수 있다.
• 값 두개가 변하면 나머지값을 알수 있다 라는 사실을 이용할텐데, A, B 를 알면 C 를 알 수 있기 떄문에 한 그룹이 가질수 있는 값 M = A+B+C check[M][M][M] -> check[M][M] 로 상태에 대한 체크를 줄일 수 있다.
• 가능성만 구하면 되기때문에 값의 위치는 상관없이 중복 체크를 하면된다
• 또한 전체가 3으로 나눠 떨어지지 않으면 무조건 0 이라는 사실을 활용해 입력에 대한 가지 치기가 가능하다.
• 시간 복잡도 O(N^2), 공간 복잡도 O(M^2) 로 상태 BFS 로 풀이 가능

코드

package gold.BJ12886GroupSton;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.StringTokenizer;

class State {
	int a;
	int b;
	int c;

	public State(int a, int b, int c) {
		this.a = a;
		this.b = b;
		this.c = c;
	}

	public boolean isSame() {
		return a == b && b == c;
	}
}

public class Main {
	static boolean[][] check; // X < Y 일때  X + X  < Y성립? yes

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int A = Integer.parseInt(st.nextToken());
		int B = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		check = new boolean[A + B + C + 1][A + B + C + 1]; // 조합의 중복을 체크 해야한다. 총합은 같으니 마지막하나는 몰라도 된다 2차원으로 가능
		if ((A + B + C) % 3 != 0) {
			System.out.println(0);
			return;
		}
		System.out.println(bfs(A, B, C));


	}

	public static int bfs(int a, int b, int c) {

		Queue<State> q = new ArrayDeque<>();
		q.add(new State(a, b, c));
		while (!q.isEmpty()) {
			State curState = q.poll();
			if (curState.isSame()) {
				return 1;
			}

			if (curState.a != curState.b) {
				int[] ab = {curState.a, curState.b};
				int[] calAB = cal(ab);
				State nextState = new State(calAB[0], calAB[1], curState.c);
				if (calAB[0] >= 0 && calAB[1] >= 0 && !check[calAB[0]][calAB[1]]) {
					check[calAB[0]][calAB[1]] = true;
					q.add(nextState);

				}
			}
			if (curState.b != curState.c) {
				int[] bc = {curState.b, curState.c};
				int[] calBC = cal(bc);
				State nextState = new State(curState.a, calBC[0], calBC[1]);
				if (calBC[0] > 0 && calBC[1] > 0 && !check[calBC[0]][calBC[1]]) {
					check[calBC[0]][calBC[1]] = true;
					q.add(nextState);
				}
			}
			if (curState.a != curState.c) {// 앞에서 체크를 해버리면?
				int[] ac = {curState.a, curState.c};
				int[] calAC = cal(ac);
				State nextState = new State(calAC[0], curState.b, calAC[1]);
				if (calAC[0] > 0 && calAC[1] > 0 && !check[calAC[0]][calAC[1]]) {
					check[calAC[0]][calAC[1]] = true;
					q.add(nextState);
				}
			}

		}

		return 0;
	}

	public static int[] cal(int[] input) {
		int[] res = {-1, -1};
		int x;
		int y;
		// 둘다 양수여야하는데..
		if (input[0] < input[1]) {// 첫번쨰가 작을때
			x = input[0];
			y = input[1];
			//, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 만든다.
			x += input[0];
			y -= input[0];
			res[0] = x;
			res[1] = y;
		} else { // 첫번째가 클때
			x = input[1];
			y = input[0];
			x += input[1];
			y -= input[1];
			res[1] = x;
			res[0] = y;

		}
		return res;

	}
}