[JAVA] 백준 2981번 - 검문

 

📖 문제

 

📋 코드

import java.util.*;
public class Main {
	
	public static int GCD(int a, int b) {
		
		if(b == 0) return a;
		else return GCD(b, a%b);
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int num[] = new int[N];
		for (int i = 0; i < N; i++) {
			num[i] = sc.nextInt();
		}
		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/2; i++) {
			if(gcd%i==0) System.out.print(i+" ");
		}
		System.out.print(gcd+" ");
				
	}
}

👨🏻‍💻 결과

 

 

📕 풀이 방법

유클리드 호제법을 사용하여

num[0] = q[0]*gcd1 + r
num[1] = q[1]*gcd2 + r
num[2] = q[2]*gcd3 + r
...
...
...
num[n] = q[n]*gcdn + r

이라고 할 때

num배열: 입력받은 수
q배열: 우리가 알 수 없는 수들의 집합
M: 공약수들
r: 나머지 

입니다.

num 배열을 오름차 순으로 정렬한 뒤 위의 식을 좀 조작해보면

num[1] - num[0] = (q[1] - q[0])*gcd1
num[2] - num[1] = (q[2] - q[1])*gcd2
...
...
...
num[n] - num[n-1] = (q[n] - q[n-1])*gcdn

이 되고

gcd1, gcd2,... gcdn의 최대공약수가 위 문제에서 구해야 하는 나머지 M 중에서 가장 큰 수가 됩니다.

int gcd = num[1]-num[0];
for (int i = 2; i < N; i++) {
	gcd = GCD(gcd, num[i]-num[i-1]);
}

 

 

예를 들어

[입력1]
3
6
34
38

num배열의 값들을 오름차 순으로 정렬하면
num[0] = 6
num[1] = 34
num[2] = 38
이고

num[1] - num[0] = 28
num[2] - num[1] = 4
이며, 2개의 수들의 공통되는 최대 공약수를 구하면
4가 나오며, 답은 '2 4'

 

[입력2]
5
5
17
23
14
83

num배열의 값들을 오름차 순으로 정렬하면
num[0] = 5
num[1] = 14
num[2] = 17
num[3] = 23
num[4] = 83
이고

num[1] - num[0] = 9
num[2] - num[1] = 3
num[3] - num[2] = 6
num[4] - num[3] = 60
이며, 4개의 수들의 공통되는 최대 공약수를 구하면
3이 나오며 답은 '3'

 

 

 

🔗 링크

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

2981번: 검문