[자바] 백준 12886 - 돌 그룹 (java)

목차

문제 : boj12886

 

 

필요 알고리즘

• 그래프 탐색
  
  • 의외로 탐색 문제이다!

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  아이디어 문제이다. 예를들어 10개의 정수 중 8개 정수의 합이 100인 정수 8개가 존재하는지 알아내야 한다고 해보자. 직관적으로 우린 그냥 나머지 2개의 합이 '전체의합-100'인 2개가 존재하는지 찾게 될 것이다.

 

  이 문제도 나머지의 관점에서 생각해보자. S=A+B+C라고 해보자. 이 때 A,B,C 중 어떤 2개를 선택하든지 전체의 합에 변함은 없다. 따라서 3개 중 2개의 값을 안다면 우린 나머지 1개의 값도 안다고 할 수 있다. 즉, 3개를 동시에 탐색하지 않고 2개씩만 탐색해도 된다. 이게 왜 중요하냐면, A,B,C 3개를 가지고 만들어질 수 있는 모든 경우의 수는 O(1500^3) 정도 되겠지만, 2개만 가지고 놀면 O(1500^2) 정도면 될 것이기 때문이다. 1500은 대충 이 문제에서 계산 중 나올 수 있는 최대 정수이다.

 

  T=S/3 이라고 해보자. 이 때 방문체크 v[x][y]를 x돌과 y돌의 조합이 나온 경우라고 해보자. 이 경우 나머지 공 하나는 S-x-y 일 것이고, x==y==T 라면 정답이 존재하는 경우이다. 즉 모든 탐색 후 v[T][T] 가 존재했다면 1, 아니면 0을 출력하면 된다. bfs, dfs 등 아무 그래프 탐색 방식이나 써서 진행하면 된다.

private void find(int a, int b) {
    if (a==t && b==t) possible = true;	// 3개 중 2개가 (A+B+C)/3 이라면 가능한 경우
    if (possible || a==b || v[a][b] || v[b][a]) return;	// 이미 방문한 조합이거나 동일한 수라면 무시
    v[a][b] = true;	// 이미 방문한 조합 체크

    int c = s-a-b;	// 나머지 하나의 수는 전체의 합에서 a,b를 빼주면 알 수 있다.
    if (a<b) {	// 문제에서 제시된 방식으로 진행
        b-=a;
        a*=2;
    } else {
        a-=b;
        b*=2;
    }

    find(a, b);	// 다음 조합 진행
    find(b, c);
    find(a, c);
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    boolean[][] v = new boolean[2000][2000];
    int s, t;
    boolean possible = false;

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        s = a+b+c;
        if (s%3!=0) {
            System.out.println(0);
            return;
        }
        t = s/3;

        find(a, b);
        find(b, c);
        find(a, c);

        System.out.println(possible?1:0);
    }

    private void find(int a, int b) {
        if (a==t && b==t) possible = true;
        if (possible || a==b || v[a][b] || v[b][a]) return;
        v[a][b] = true;

        int c = s-a-b;
        if (a<b) {
            b-=a;
            a*=2;
        } else {
            a-=b;
            b*=2;
        }

        find(a, b);
        find(b, c);
        find(a, c);
    }
}