[백준 2981] - [수학 최대공약수] - 검문 (JAVA)

문제 링크 : https://www.acmicpc.net/problem/2981

---

이 문제는 정답률에서도 나오듯이 극악의 문제이다. 

왜 극악이라 하냐면 쓸데없는데서 시간을 낭비 했기에 극악의 문제로 생각한다.

6 34 38  총 3개의 수가 주어지고 종이에 적은수 M으로 나누었을때 나머지가 모두 같게 되는 모든 M을 찾아 보기위해 노력 해봤다.

처음에는 시간초과가 발생했다. 

시간초과를 발생하게한 방식은 다음과 같다. 

입력 받은 수의 배열 arr에서 

인덱스 1번부터 arr.length-2 까지 반복하면서 

i 기준 arr[i] - arr[i-1]  , arr[i+1] - arr[i]  두 수의 최대 공약수를 구하고 그 최대 공약수중에서 제일 작은 최대 공약수의 약수를 반환했다. 

결과는 제대로 나왔다. 

하지만 시간 초과에 걸렸다. 

시간초과 소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        
        long[] arr = new long[size];
        
        long[] dist = new long[size];
        
        for(int i=0; i < size; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(arr);
        
        long result = 1000000000;
        
        for(int i=1; i < size-1; i++) {
            long dist1 = arr[i] - arr[i-1];
            long dist2 = arr[i+1] - arr[i];
            
            long gcd = getGCD(Math.max(dist1, dist2), Math.min(dist1, dist2));
            
            result = Math.min(result, gcd);
        }
        
        StringBuilder sb = new StringBuilder();
        
        for(int i=2; i <= result/2; i++) {
            if(result % i == 0) sb.append(i + " ");
        }
        sb.append(result);
        
        System.out.println(sb.toString());
        
        br.close();
    }
 
    public static long getGCD(long a, long b) {
        if(b == 0) return 0;
        
        while(b > 0) {
            long tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
}

위의 소스는 시간초과가 나서 실패한 소스다. 

위의 소스에서 시간초과가 발생하는 이유가 두가지가 있다. 

제일 큰 이유는 34번째 줄 약수를 구하는 부분에서 많은 시간을 잡아먹었다. 

그리고 최대 공약수를 구하는 대상이 잘못됐다. 인덱스 값들의 차로 계산을 한다면 차가 1억쯤 나는 값들을 받을 경우 많은 시간을 잡아 먹을거 같았다. 

다시한번 문제를 읽어보니 문제에 힌트가 있었다. 

수 1 ~ N을 M으로 나눴을때 나머지가 모두 같아야 한다.

이 조건으로 식을 작성해보았다.

A[1] % M = A[1] - (A[1] / M) * M

A[2] % M = A[2] - (A[2] / M) * M

A[3] % M = A[3] - (A[3] / M ) * M

.

.

.

이고 A[1] % M= A[2] % M= A[3] % M 이니깐 

A[1] - (A[1] / M ) * M = A[2] - (A[2] / M) * M 도 성립이 된다.

이 값을 치환을 해보면

A[1] - A[2] = M * (A[1] / M  -  A[2] / M) 

A[2] - A[3] = M * (A[2] / M  -  A[3] / M) 

A[3] - A[4] = M * (A[3] / M  -  A[4] / M) 

A[N-1] - A[N] = M * (A[N-1] / M - A[N] / M )

여기에서 추론할 수 있는 공통점은 전부 같은 나머지를 갖을경우 어느 수에서 다른 수를 뺄 경우 공통된 M이라는 값을 가진다는 것이다.

그럼 M은 어떻게 구할 수 있을까??

공통된 값 M을 가지고 있다면 서로 서로소가 되지 않는다는거고 공약수가 있을것이란 말이 된다.

A[1] - A[0] 에서 A[I] - A[i-1] 까지의 최대 공약수를 구하고 구해진 최대 공약수의 약수를 뽑아 내면 되겠다. 

사실 이 문제를 쉽게 이해했는데 설명을 하기가 엄청 힘들다.

쉽게 이해한 이유는 문제를 잘못읽고 잘못풀었는데 그게 운이 좋게 맞는 방법이었다. 

나는 애초에 간격을 M으로 나누었을때 나머지가 같은 M을 찾으라는줄 알고 애초에 이렇게 풀었는데 문제를 다시 읽어보니 달라서 당황했다. 

앞으로는 문제를 꼼꼼히 읽어야 겠다. 

그리고 이문제를 잘못 푼다면 시간초과는 당연하거니와 메모리 초과도 발생한다. 

만약에 마지막에 구해진 최대 공약수의 약수를 구할 경우 잘못하다가는 메모리 초과에 걸리기 때문에 조심해서 문제를 풀어보자. 

나는 바보같은 실수를 해서 메모리초과가 발생했다.

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        
        int[] arr = new int[size];
        
        for(int i=0; i < size; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        
        int gcd = arr[1] - arr[0];
        
        for(int i=2; i < size; i++) {
            int dist1 = arr[i] - arr[i-1];
            
            gcd = getGCD(gcd, dist1);
        }
        
        dividers(gcd);
    }
 
    public static int getGCD(int a, int b) {
        if(b == 0) return 0;
        
        while(b > 0) {
            int tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
    
    private static void dividers(int num){
        List<Integer> list = new LinkedList<>();
        list.add(num);
        
        for (int i = 2; i <= Math.sqrt(num); i++)
        {
            if (num % i == 0)
            {
                if (i == num / i)
                    list.add(i);
                else
                {
                    list.add(i);
                    list.add(num / i);
                }
            }
        }
        Collections.sort(list);
        
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < list.size(); i++)
            sb.append(list.get(i) + " ");
        System.out.println(sb.toString());
    }
}