[BOJ] 2981번 : 검문 (JAVA/자바)

문제

---

알고리즘 고민

처음에는 단순하게 모든 숫자를 다 나눠보면서  나머지가 같은 숫자들을 나열하는 방식으로 하려했으나 당연스럽게도 시간초과로 인해 실패했다. 그 이후에 여러가지 방법을 시도하다가 실패하고 https://st-lab.tistory.com/155 사이트의 풀이를 참고하여 풀었다. (정말 잘푸시는거 같다...)

 

먼저, 수학적인 수식으로 접근을 해서 공통적인걸 뽑아내는 과정을 거쳤다.

특정한 숫자로 나눴을때 모든 숫자가 나머지가 같아야 하는 문제의 조건에 식을 맞춰서 작성한다면 다음과 같이 수식을 만들 수 있다. 최대 공약수를 M 이라고 하고 n번째의 숫자를 N, 나머지를 r 이라고 하였다.

$N_1 = M * n_1 + r$

$N_2 = M * n_2 + r$

$N_3 = M * n_3 + r$

...

$N_n = M * n_n + r$

 

그렇다면 나머지가 같기때문에 수식을 정리해보자면 $N_2 - N_1 = M (n_2 - n_1) + (r - r)$ 이라고 할 수 있다. 따라서, $N_2 - N_1 = M (n_2 - n_1)$ 이 되므로 $M$ 은 $N_2 - N_1$ 의 약수라고 볼 수 있다.

 

이렇게 모든 숫자를 나열하면

$N_2 - N_1 = M (n_2 - n_1)$

$N_3 - N_2 = M (n_3 - n_2)$

$N_4 - N_3 = M (n_4 - n_3)$

이렇게 볼 수 있다.

 

그렇다면 이때의 M은 $N_1, N_2, N_3, ..., N_n$ 숫자들의 공통된 나머지 r 을 가지는 숫자이면서 

$N_2 - N_1, N_3 - N_2, N_4 - N_3$ 숫자들의 약수 라고 볼 수있다. 그러므로 최대 M을 찾고 그 수의 약수들을 나열해준다면 해당하는 숫자는 입력받은 숫자 $N_1, N_2, N_3, ..., N_n$들을 나눴을때 나머지 r을 갖는 수 라고 볼 수 있다.

 

그러면 M은 어떻게 구할 수 있는가? $N_2 - N_1, N_3 - N_2, N_4 - N_3$ 숫자들의 공약수이므로 해당하는 숫자들의 최대공약수를 구해주었다. 이후 최대공약수 M의 약수들을 나열하면서 출력했다. 단, 이와 같은 방식을 진행하려면 입력받은 숫자를 오름차순으로 나열해주어서 뺀 숫자에서 음수가 생기지 않게 해야한다.

---

JAVA Code

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

public class Main {
    public static int GCD(int num1, int num2) {
        while (num2 != 0) {
            int tmp = num1 % num2;
            num1 = num2;
            num2 = tmp;
        }

        return num1;
    }

    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);
        for (int i = arr.length - 1; i > 0; i--) {
            arr[i]-=arr[i-1];
        }

        int gcd = arr[1];
        for (int i = 2; i < size; i++) {
            gcd = GCD(gcd, arr[i]);
        }

        StringBuffer sb = new StringBuffer();
        for (int i = 2; i <= gcd; i++) {
            if(gcd%i==0) sb.append(i).append(' ');
        }

        System.out.println(sb.toString().strip());
    }
}

---

이런 문제가 제일 힘든거같다... 구현은 빨리 할 수 있는데 방법이 아예 생각이 안난다..