Yunseok Byeon

Yunseok Byeon

Motivational Speaker

백준 2981번 : 검문

1. 문제 설명 (2981)

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

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

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

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

2. 분류

3. 풀이

유클리드 호제법 으로 간단하게 풀이할 수 있는 문제이다. 하지만 당연하게도, 처음부터 끝까지 무모하게 GCD 를 구하다가 시간 초과로 틀렸다.

먼저 유클리드 호제법 은 다음과 같다.

유클리드 호제법

두 양의 정수 a, b (a > b) 에 대하여 a = bq + r (0 <= r < b)라 하면, a, b의 최대공약수 는 b, r의 최대공약수 와 같다. 즉, GCD(a, b) = GCD(b, r)
r = 0이라면, a, b의 최대공약수는 b가 된다. (출처:나무위키)

이미 증명된 사항이므로 각설하고 필요한 부분만 살펴보면 다음과 같다.

  1. a > b 의 경우에 위의 수식이 성립.
  2. M 으로 나누었을 때 나머지가 r 로 모두 같다.

따라서 문제의 상황을 생각해보면 아래와 같은 식이 구해진다.

  1. a1 = M * q1 + r
  2. a2 = M * q2 + r

위의 1. 에서 2. 을 빼면 다음과 같다.

a1 - a2 = M * (q1 - q2)

따라서 N개의 수에 대해 위의 과정을 반복하며 M 값의 최댓값을 구해주고, M 의 약수들을 출력하면 된다…로 이해했다.

a > b 의 경우에 성립하므로 먼저 Arrays.sort 를 통해 정렬한 후, 다음과 같은 GCD 함수 를 활용해 풀이했다. (출처:나무위키)

1
2
3
4
5
6
7
int GCD(int n1, int n2) {
    int r = n1 % n2;
    if(r == 0)
        return n2;
    else
        return GCD(n2, r);
}
cs


4. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.io.*;
import java.util.*;
 
public class Q2981 {
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        int[] num = new int[N];
        for(int i = 0; i < N; i++)
            num[i] = Integer.parseInt(br.readLine());
        
        Arrays.sort(num);
        int gcd = num[1] - num[0];
        
        for(int i = 2; i < N; i++)
            gcd = GCD(gcd, num[i] - num[i-1]);
        
        for(int i = 2; i <= gcd; i++) {
            if(gcd % i == 0)
                bw.write(i + " ");
        }
        bw.flush();
        bw.close();
    }
    
    public static int GCD(int n1, int n2) {
        int r = n1 % n2;
        if(r == 0)
            return n2;
        else
            return GCD(n2, r);
    }
}
cs


5. 결과

result image

(무수한 시간 초과 흔적) 1496ms로 작동한다.

댓글남기기

참고