[JAVA]백준 알고리즘 2981번 : 검문

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

2981번: 검문

문제

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

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

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

풀이

입력된 수들을 M으로 나누었을 때 나머지가 같은 M을 찾는 문제이다.

혼자 풀었을 때 시간초과가 발생했고, 스스로 해결하지 못해 다른 블로거님의 풀이를 참고하여 풀었다.

 

A, B, C를 M으로 나누었을 때 나머지가 같다는 것을 식으로 표현하면 다음과 같다.(r : 나머지)

A = M * a + r

B = M * b + r

C = M * c + r

 

여기서 나는 A, B, C에서 각각 r을 빼면 M의 배수라는 것을 이용하여 문제를 풀어보았고, 시간초과가 발생했다.

그 블로거님은 A - B, B - C가 M의 배수라는 것을 이용하여 해결하셨다. { A - B = M * a + r - M * b - r = M * (a - b) }

 

이를 이용하면 다음은 어렵지 않다.

A - B, B - C의 최대공약수를 유클리드 알고리즘을 활용하여 구하고 최대공약수의 약수를 구하면 된다.

 

단, 주의할 점이 하나 있다.

네 개 이상의 수(여기선 네 개의 수) A, B, C, D 가 있을 때,

A - B와 B - C의 최대공약수를 구하고, B - C와 C - D의 최대공약수를 구하는 것이 아니라,

A - B와 B - C의 최대공약수를 G라고 하면 그다음에는 G와 C - D의 최대공약수를 구해야 한다.

G는 A - B와 B - C의 공약수 중 가장 큰 수이고, 그것과 C - D의 최대공약수를 구해야 A - B, B - C, C - D의 최대공약수가 되기 때문이다.

 

findG 함수는 유클리드알고리즘을 재귀함수로 구현한 것이다.

코드

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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] inputNUM = new int[N];

        for(int i = 0; i < N; i++) {
            inputNUM[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(inputNUM);

        int G = inputNUM[1] - inputNUM[0];

        for(int i = 1; i < N - 1; i++) {
            G = findG(G, inputNUM[i+1] - inputNUM[i]);
        }

        for(int i = 2; i <= G / 2; i++) {
            if(G % i == 0) sb.append(i).append(" ");
        }
        sb.append(G);
        System.out.println(sb);
    }
    public static int findG(int a, int b) {
        if(b > a) {
            int tmp = a;
            a = b;
            b = tmp;
        }

        int r = a % b;
        if(r == 0) return b;
        return findG(b, r);
    }
}

틀린 부분이 있다면 정정해주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!