[BaekJoon] 백준 12868번. 돌 그룹

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

12886번: 돌 그룹

 

 

 

풀이 : 

A, B, C 3개의 돌이 주어 졌을 때 2개의 조합을 선택하여 연산을 수행했을 때 모두 같은 값이 될 수 있도록 확인한다. 

 

예를 들어 A, B 를 선택했고, A < B 일 경우

A = A + A, B = B - A 으로 새로 값을 정할 수 있다. 

 

여기서 접근 방법은

A, B, C 을 모두 더한 값이 달라지지 않는다는 것이다. 

 

합이 달라지지 않기에 2가지 조합만 생각해도 나머지 1개의 값이 정해지게 된다. 

또한 돌에 순서가 존재하지 않기에 이미 연산된 조합이라면 무시해야 한다. 

 

 

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

public class Main {
    static boolean[][] visited;
    static int flag;
    static int sum;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] abc = br.readLine().split(" ");
        
        int a = Integer.parseInt(abc[0]);
        int b = Integer.parseInt(abc[1]);
        int c = Integer.parseInt(abc[2]);
        
        flag = 0;
        sum = a + b + c;
        
        visited = new boolean[1501][1501];
        
        if ( (a + b + c) % 3 != 0) {
            System.out.println(flag);
        } else {
            visited[a][b] = true;
            visited[b][a] = true;
            dfs(new int[]{a, b, c});
            System.out.println(flag);
        }
    }
    
    public static void dfs(int[] num) {
        if (num[0] == num[1] && num[1] == num[2]) {
            flag = 1;
            return;
        }
      
        for(int i = 0; i<3; i++) {
            for(int j = i+1; j<3; j++) {
                if (num[i] != num[j]) {
                    int ni = num[i] > num[j] ? num[i] - num[j] : num[i] + num[i];
                    int nj = num[i] > num[j] ? num[j] + num[j] : num[j] - num[i];
    
                    if (!visited[ni][nj]) {
                        // ni, nj 조합이나 nj, ni 조합이 같음 
                        visited[ni][nj] = true;
                        visited[nj][ni] = true;
                        dfs(new int[]{ni, nj, sum - ni - nj});
                    }
                }
            }
        }
        
    }
}