[백준]#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

풀이

이 문제는 DFS 알고리즘을 이용해서 돌 갯수 계산을 진행해서 풀었다. 추가로 이미 계산한 돌 갯수는 반복하지 않기 위해 boolean 2차원 배열을 이용했다.

import java.io.InputStreamReader;
import java.io.BufferedReader;


public class Main {
    static boolean[][] visited = new boolean[1505][1505];
    static int ans = 0;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int a = Integer.parseInt(input[0]);
        int b = Integer.parseInt(input[1]);
        int c = Integer.parseInt(input[2]);

        dfs(a, b, c);
        System.out.println(ans);
    }

    public static void dfs(int a, int b, int c) {
        if(a==b && b==c) {
            ans = 1;
            return;
        }

        if(a<b && !visited[a][b]) {
            visited[a][b] = true;
            visited[b][a] = true;
            dfs(2*a, b-a, c);
        }

        if(b<a && !visited[b][a]) {
            visited[a][b] = true;
            visited[b][a] = true;
            dfs(a-b, 2*b, c);
        }

        if(a<c && !visited[a][c]) {
            visited[a][c] = true;
            visited[c][a] = true;
            dfs(2*a, b, c-a);
        }

        if(c<a && !visited[c][a]) {
            visited[a][c] = true;
            visited[c][a] = true;
            dfs(a-c, b, 2*c);
        }

        if(c<b && !visited[c][b]) {
            visited[c][b] = true;
            visited[b][c] = true;
            dfs(a, b-c, 2*c);
        }

        if(b<c && !visited[b][c]) {
            visited[c][b] = true;
            visited[b][c] = true;
            dfs(a, 2*b, c-b);
        }
    }
}