[백준 - 12886][Gold 4] - 돌 그룹(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을 출력한다.

 

단순 구현으로 풀릴까?

---

우선 가장 쉬운 방법인 구현을 생각해보자.

 

우선 모든 수가 같아야 하므로 각 숫자는 세가지 수의 합 / 3 이어야 한다. 그러므로 3의 배수가 아니면 에초에 나눌 수 없으므로 제외시킨다.

 

숫자 3개 중 2개를 골라 같지 않으면 큰 수 는 작은수를 빼고 작은 수는 2배를 시켜 다음 경우의 수로 넘기면 될 것이다. 이때 이미 처리했던 경우의 수라면 다시 방문할 필요가 없으므로 제외시킨다.. 계속 진행하다가 모든 숫자가 같으면 가능하다고 출력하고 모든 경우의 수를 다 탐색했는데 모든 수가 같지 않으면 불가능하다고 출력하면 될 것이다.

 

이를 시간복잡도를 계산하면 다음과 같다.

 

O(N)
= (A의 경우의수) * (B의 경우의수) * (C의 경우의 수)
= N^3

 

이 때 입력값의 최대값은 500이지만 모든 숫자가 더해질 경우가 있으므로 최대 숫자는 1500이다. 그러므로 시간복잡도를 계산하면 1,500*1,500*1,500 = 3,375,000,000이므로 주어진 시간인 2초의 예상 연산 횟수인 2억보다 크다. 그러므로 해당 방법으로 하면 시간 초과가 날 것이다.

 

정말 구현으로 풀면 시간 초과가 날까??

---

만약 위의 방법으로 풀면 시간 초과가 나는지 실험해보면 아래와 같은 결과가 나온다.

 

 

 

이상하다. 시간 초과 보다 메모리 초과가 먼저 발생한다. 왜냐하면 위의 방법으로 방문 배열을 생성하면 1,500*1,500*1,500이기 때문에 방문배열만 약 3,200mb를 소모하게 된다. 그러므로 메모리제한인 512mb를 넘기 때문에 메모리 초과가 발생한 것이다.

이를 해결하기 위해선 모든 숫자의 합은 일정하다는 점을 이용하면 된다. 우리는 A와 B만 알아도 C의 값을 알 수 있다. 왜냐하면 A+B+C의 값은 변하지 않으므로 A+B값을 빼면 C값이 나오기 때문이다. 이 법칙을 이용하면 우리는 방문 배열을 1,500*1,500으로 감소할 수 있다. 즉 숫자 1개의 경우의 수를 몰라도 구할 수 있기 때문에 방문 배열 크기를 줄일 수 있다! 

위를 반영한 시간 복잡도는 다음과 같다.

O(N)
= (A의 경우의수) * (B의 경우의수)
= N^2

 

시간 복잡도가 N^3에서 N^2로 감소되었음을 확인할 수 있다. N은 앞서 말한대로 최대 1,500이기 때문에 최대 연산 수는 1,500*1,500 = 2,250,000 으로 2억보다 작다. 그러므로 우리는 제한된 메모리와 시간이내로 문제를 해결할 수 있다!

 

해결 코드

---

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

public class Main {
    public static void main(String[] args) throws Exception {
        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());

        System.out.println(validSameStone(A,B,C));
    }

    public static int validSameStone(int A, int B, int C){
        if((A+B+C)%3 !=0){
            return 0;
        }

        boolean[][]visited = new boolean[1501][1501];

        Queue<int []> q = new LinkedList<>();
        q.add(new int[]{A,B,C});

        visited[A][B] = true;

        while(!q.isEmpty()){
            int[] curr = q.poll();

            if(curr[0] == curr[1] && curr[1] == curr[2]){
                return 1;
            }
			
            //2개의 돌을 선택
            for(int i=0;i<curr.length;i++){
                for(int j=0;j<curr.length;j++){
                    int X = curr[i];
                    int Y = curr[j];

                    if(X >= Y){
                        continue;
                    }
					
                    //선택되지 않은 나머지 돌 인덱스
                    int k = 3 - i - j;

                    int[] next = new int[3];
                    next[i] = X+X;
                    next[j] = Y-X;
                    next[k] = curr[k];

                    if(isValid(next,visited)){
                        visited[next[0]][next[1]] = true;
                        q.add(next);
                    }
                }
            }
        }

        return 0;
    }

	//다음 돌이 가능한지 판단하는 메소드
    public static boolean isValid(int[] stone,boolean[][] visited){
        if(stone[0] <0 || stone[1] <0){
            return false;
        }
        if(stone[0] >= visited.length || stone[1] >= visited.length){
            return false;
        }
        if(visited[stone[0]][stone[1]]){
            return false;
        }
        return true;
    }
}

 

 

실행 결과

---

 

 

제한시간인 2초안에 문제가 해결되었다!

 

팁

---

 

• 메모리 초과가 발생하면 주로 큐에 값이 너무 많이 들어갔거나 배열의 크기 문제이다.
• 수가 일정한 집합이라면 나머지 1개의 값은 다른 나머지 합으로 구할 수 있다.