문제

이해

A, B, C 그룹에 돌의 개수가 주어집니다. 각 그룹에는 최대 500개가 주어질 수 있습니다.

각 그룹에 대해 연산을 수행합니다. 연산 과정은 다음과 같습니다..

크기가 같지 않은 두 그룹을 선택한다. 두 그룹의 크기를 비교하여 큰 그룹에서 작은 그룹의 크기만큼 작은 그룹으로 옮긴다. 다시 말해, x = x + x, y = y - x (x < y) 연산을 수행하는 것이다.

연산을 수행하여 각 그룹의 크기가 모두 같아질 수 있다면 1을, 불가능하다면 0을 출력합니다.

접근

단순하게 그리디로 접근하기엔 어려워보입니다. 연산으로 발생하는 세 그룹의 경우의 수가 많기도 하며 규칙도 찾기 어렵습니다. 따라서, 조건을 만족하는 상태가 될 때까지 탐색하는 것이 좋아보입니다.

탐색하는 방법에 대해 생각해봅시다. 탐색의 기준은 연산의 내용을 보면 되겠습니다. 연산은 두 그룹을 선택하고 비교하여 그룹의 상태를 조정합니다. 항상 세 그룹밖에 존재하지 않기 때문에 연산이 수행되는 경우의 수는 (A, B), (B, C), (C, A) 밖에 존재하지 않습니다.

탐색의 종료 조건은 A == B == C이기 때문에 BFS를 수행하는 것이 적절해보입니다. 그렇다면 BFS의 중복관리는 어떻게 하면 될까요? A, B, C 세그룹이 존재하기 때문에 각 그룹이 가질 수 있는 값을 방문 기준으로 삼을 수 있겠습니다. 따라서, visited[1501][1501][1501]이라고 생각할 수 있습니다.

1500^3은 매우 큰 수이기 때문에 자원이 부족해보입니다. 줄이기 위한 방법에 대해서 생각해봅시다. A, B, C는 모두 정해진 범위 안에서 움직입니다. 다시 말해, 세 그룹 중 두 그룹의 값이 정해진다면 나머지 한 그룹의 값도 정해집니다. 또한, 우리는 A, B, C의 조합에 대해서는 관심이 없습니다.

(A, B, C)가 (100, 200, 300) 혹은 (200, 100, 300) 혹은 (300, 100, 200) 인지 관심없습니다. 결국 모두 같은 경우라고 생각해야 합니다.

따라서, 세 그룹의 상태를 특정짓기 위해선 두 그룹의 정보만 있으면 됩니다. visited[1501][1501]으로 줄일 수 있습니다.

정리해보겠습니다.

1. 조건에 만족하는 경우를 탐색하자.
2. BFS를 수행하되 1500x1500 배열로 중복처리하자.

풀이

위 과정에 유의하여 BFS 코드를 작성하면 되겠습니다.

단, 세 그룹의 초기값의 합이 3의 배수가 아니라면 어떻게 연산을 수행해도 같은 값을 가지지 못합니다.

따라서, 해당 조건을 예외처리하여 시간을 줄일 수 있습니다.

코드

package baekjoon;

import java.util.*;
import java.io.*;

public class prob12886 {
	static class Status{
    	int a, b, c;
    	
    	Status(int a, int b, int c){
    		this.a = a;
    		this.b = b;
    		this.c = c;
    	}
    }
	static int A, B, C;
	
    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	A = Integer.parseInt(st.nextToken());
    	B = Integer.parseInt(st.nextToken());
    	C = Integer.parseInt(st.nextToken());
    	
    	System.out.println(bfs(A, B, C) ? 1 : 0);
    }
    
    static boolean bfs(int a, int b, int c) {
    	if((a + b + c) % 3 != 0) return false;
    	
    	Queue<Status> q = new LinkedList<>();
    	boolean[][] visited = new boolean[1501][1501];
    	
    	q.add(new Status(a, b, c));
    	visited[a][b] = true;
    	int maxqsize = 0;
    	while(!q.isEmpty()) {
			maxqsize = Math.max(maxqsize, q.size());
    		Status s = q.poll();
    		
    		a = s.a;
    		b = s.b;
    		c = s.c;
    		
    		if(a == b && b == c) {
    			return true;
    		}
    		
    		if(a != b) {
    			int na = a > b ? a-b : a+a;
    			int nb = a > b ? b+b : b-a;
    			
    			if(!visited[na][nb]) {
    				q.add(new Status(na, nb, c));
    				visited[na][nb] = true;
    			}
    		}
    		
    		if(b != c) {
    			int nb = b > c ? b-c : b+b;
    			int nc = b > c ? c+c : c-b;
    			
    			if(!visited[nb][nc]) {
    				q.add(new Status(a, nb, nc));
    				visited[nb][nc] = true;
    			}
    		}
    		
    		if(a != c) {
    			int na = a > c ? a-c : a+a;
    			int nc = a > c ? c+c : c-a;
    			
    			if(!visited[na][nc]) {
    				q.add(new Status(na, b, nc));
    				visited[na][nc] = true;
    			}
    		}
    		
    	}
    	
    	return false;
    }
}

결과