[백준 12886번] 돌 그룹(java)

문제

오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 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. A B C가 같은 숫자가 되야한다.
2. A>B이면 A = A+A, B = B-A이다 (A+A)+(B-A)+C = A+B+C 이다.
3. 결론은 주어진 3 숫자의 총합은 변하지 않는다였다.
4. 그렇다면 A와 B만 있어도 C의 값을 알수있게 되었다. 그 말은 A,B로만 조합을 만들어 비교하면 된다.
5. 또한 A+B+C 값이 3으로 나눠지지 않는다면 이 조합은 같은숫자로 나눌수 없다는 뜻이였다.
   모든 조건을 찾았으니 위 조건에 따라 너비 탐색을 실행하면 된다.

첫번째 코드는 숫자들의 합과 나머지값을 이용해 푼 코드이고 두번째 코드는 문자열을 이용해서 비교한 코드이다

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

public class Main {
    static boolean flg = false;
    static Queue<Com> que = new LinkedList<Com>();
    static boolean [][] visited = new boolean[1501][1501];
    public static class Com{
        int a,b,c;
        public Com(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
    //숫자 비교 함수
    public static void Calcul(int da, int db, int dc) {

    }
    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());

        if((a+b+c)%3 !=0) {
            System.out.println("0");
            return;
        }

        Com com = new Com(a,b,c);
        que.add(com);
        visited[a][b] = true;
        boolean flg = false;
        while(!que.isEmpty()) {
            Com node = que.poll();
            if(node.a == node.b && node.b == node.c) {
                flg=true;
                break;
            }
            //a랑 b비교
            if(node.a != node.b) {
                if(node.a<node.b) {
                    if(!visited[node.a+node.a][node.b-node.a]) {
                        que.add(new Com(node.a+node.a,node.b-node.a,node.c));
                        visited[node.a+node.a][node.b-node.a] = true;
                    }
                }else if(node.a>node.b) {
                    if(!visited[node.a-node.b][node.b+node.b]) {
                        que.add(new Com(node.a-node.b,node.b+node.b,node.c));
                        visited[node.a-node.b][node.b+node.b] = true;
                    }
                }
            }
            //a랑 C비교
            if(node.a != node.c) {
                if(node.a<node.c) {
                    if(!visited[node.a+node.a][node.c-node.a]) {
                        que.add(new Com(node.a+node.a,node.b,node.c-node.a));
                        visited[node.a+node.a][node.c-node.a]=true;
                    }
                }else if(node.a>node.c) {
                    if(!visited[node.a-node.c][node.c+node.c]) {
                        que.add(new Com(node.a-node.c,node.b,node.c+node.c));
                        visited[node.a-node.c][node.c+node.c]=true;
                    }
                }
            }
            //b랑 c비교
            if(node.b != node.c) {
                if(node.b<node.c) {
                    if(!visited[node.b+node.b][node.c-node.b]) {
                        que.add(new Com(node.a,node.b+node.b,node.c-node.b));
                        visited[node.b+node.b][node.c-node.b]=true;
                    }
                }else if(node.b>node.c) {
                    if(!visited[node.b-node.c][node.c+node.c]) {
                        que.add(new Com(node.a,node.b-node.c,node.c+node.c));
                        visited[node.b-node.c][node.c+node.c]=true;
                    }
                }

            }
        }
        if(flg) {
            System.out.println("1");
        }else {
            System.out.println("0");
        }
    }
}

문자열 이용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static boolean flg = false;
    static Queue<Com> que = new LinkedList<Com>();
    static HashSet<String> visited = new HashSet<String>();
    static ArrayList<Integer> forsort = new ArrayList<Integer>();
    public static class Com{
        int a,b,c;
        public Com(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }
    }
    //숫자 비교 함수
    public static void Calcul(int da, int db, int dc) {
        int xx;
        int xy;
        if(da == db) {
            return;
        }
        if(da>db) {
            xx = db*2;
            xy = da-db;
        }else {
            xx = da*2;
            xy = db-da;
        }
        forsort.clear();
        forsort.add(xx);
        forsort.add(xy);
        forsort.add(dc);
        Collections.sort(forsort);

        String visit = Integer.toString(forsort.get(0))+" "+Integer.toString(forsort.get(1))+" "+Integer.toString(forsort.get(2));
        //이미 확인해본 조합이면
        if(visited.contains(visit)) {
            return;
        }else {
            visited.add(visit);
            que.add(new Com(xx,xy,dc));
        }
    }
    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]);

        forsort.clear();
        forsort.add(a);
        forsort.add(b);
        forsort.add(c);
        Collections.sort(forsort);
        String visit = Integer.toString(forsort.get(0))+" "+Integer.toString(forsort.get(1))+" "+Integer.toString(forsort.get(2));
        visited.add(visit);
        que.add(new Com(a,b,c));

        //큐 빌때까지 반복
        while(!que.isEmpty()) {
            Com node = que.poll();
            if(node.a == node.b && node.b == node.c) {
                flg = true;
                break;
            }
            //조합 가능한것 넣기
            Calcul(node.a,node.b,node.c);// a b 고른 경우
            Calcul(node.a,node.c,node.b);// a c 고른 경우
            Calcul(node.b,node.c,node.a);// b c 고른 경우
        }

        if(flg) {
            System.out.println("1");
        }else {
            System.out.println("0");
        }
    }
}