[BOJ 2981] 검문 (Java)

문제

https://www.acmicpc.net/problem/2981

2981번: 검문

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

풀이

수학적인 지식이 필요한 문제이다. 

A, B, C, D 의 수가 주어지고, M으로 나눴을 때 나머지가 모두 같게 되는 M이 있다면?

아래와 같이 수를 표현할 수 있다.

A = M * a + r

B = M * b + r

C = M * c + r

D = M * d + r

 

여기서 중요한 것은 M과 r은 동일한 값이라는 것이다. 

B에서 A를 빼보자. 

B - A = (M * b + r)- (M * a + r) 

B - A = M * (b-a) 

r은 동일한 값이니 마이너스로 제거된다.

 

B - A = M * (b-a) 

C - B = M * (c-b) 

D - C = M * (d-c) 

 

M으로 나눴을 때 나머지가 모두 같다고 가정 하에, 두 수의 차이 값들이 모두 M을 약수로 가지는 것을 알 수 있다. 

이를 통해 M을 구하기 위해서는, 두 수의 차이 값들의 최대 공약수를 구한 후 최대 공약수의 모든 약수를 구하면 된다. 

 

최대 공약수 구하는 법은 유클리드 호제법을 사용한다. 

 

 

소스코드

package math;

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

public class BOJ2981 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        // 오름차순으로 정렬
        Arrays.sort(arr);

        // 차이 값의 최대공약수 구하기
        int M = arr[1] - arr[0];
        for(int i = 2; i < N; i++){
            M = getGCD(M, arr[i]- arr[i-1]);
        }
        // 최대공약수의 약수 모두 구하기
        for(int i = 2; i <= M; i++){
            if(M%i == 0) sb.append(i).append(" ");
        }
        System.out.println(sb.toString());
    }

    public static int getGCD(int a, int b){
        //great common divisor 최대공약수
        if(b > a){
            int temp = a;
            a = b;
            b = temp;
        }

        while(b != 0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}