[백준 12886 - Java] 돌 그룹

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

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

 

풀이

이 문제는 dfs알고리즘을 사용해서 해결했습니다.

방문 여부 확인을 3개를 가지고 해야하나 하는 고민을 했었는데 그럴 필요가 없더라구요!!

두 그룹의 값이 결정되면 자동으로 세번째 그룹의 크기가 결정되기 때문이에요!

그래서 visited[sum+1][sum+1]의 배열을 가지고 문제를 해결했습니다.

 

두개의 그룹을 선택해서 해당하는 연산을 하면서 방문 표시를 하고 재귀로 계속 호출해가면서 문제를 해결했습니다.

 

import java.util.Scanner;

public class Main {
	
	static int A, B, C;
	static int sum;
	static int[][] visited;
	static boolean answer = false;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		A = sc.nextInt();
		B = sc.nextInt();
		C = sc.nextInt();
		
		sum = A+B+C;
		visited = new int[sum+1][sum+1];
		
		if(sum %3 != 0) {
			System.out.println("0");
			return;
		}
		else {
			dfs(A, B);
		}
		
		System.out.println(visited[sum/3][sum/3]);
	}

	static void dfs(int a, int b) {
		if (visited[a][b] == 1) 
			return;
	    visited[a][b] = 1;

	    int[] rock = {a, b, sum - (a + b)};

	    for (int i = 0; i < 3; i++){
	        for (int j = 0; j < 3; j++){
	            if (rock[i] < rock[j]){
	                int[] temp = {a, b, sum - (a + b)};
	                temp[i] += rock[i];
	                temp[j] -= rock[i];
	                dfs(temp[0], temp[1]);
	            }
	        }
	    }
	}
}