[BOJ] 2981. 검문 - JAVA

🔗 문제

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

2981번: 검문

 

🧩 풀이 및 코드

문제 유형 : 수학, 정수론, 유클리드호제법

 

헤맸던 문제다.. 풀이 방법을 보면 어떻게 저런 생각을 해내는지 신기하다. 

문제에 나온 임의의 정수를 나타내면 다음과 같다. (M : 나눈수, r : 나머지)

 

A1 = M * a1 + r1   

A2 = M * a2 + r2

 

여기서 찾아내야 하는게 가능한 모든 M 이 되고, 나머지가 같기 때문에 r1 과 r2 가 같다. 따라서 여기서 A1 과 A2를 뺀다면

 

A1 - A2 = M * (a1 - a2) + (r1 - r2)

 

r1 - r2 = 0 이므로, A1 - A2 = M * (a1 - a2) 

 

M 은 (A1 - A2) 의 약수이므로, A1 과 A2 의 공약수가 된다. 우리는 여기서 M 을 찾아야 한다.

 

더 쉬운 이해를 위해 기호로 표시하지 말고 예시를 들어 설명하면

 

6 / M + r

34 / M + r

38 / M + r

 

(6 / M + r) - (34 / M + r) 을 풀어서 다시 묶어 표현하면

(6 - 34) / M 이라는 식이 나온다.

 

다음으로 (34 / M + r) - (38 / M + r) 을 풀어서 다시 묶어 표현하면

(34 - 38) / M 이라는 식이 나온다.

 

그리고 M은 모두 같다는 의미는 (6 - 34) / M 라는 식과, (34 - 38) / M 의 M이 같다는 말이고,

다르게 표현하면 M은 (6 - 34)와 (34 - 38)의 공약수라는 의미라는 것.

 

그러면 이제 공약수를 찾을 일만 남았다. 공약수를 찾는 방법은 매우 쉽지 않은가?

최대공약수가 무엇인가? 최대공약수는 '공약수들 중에서 가장 큰 값' 아니던가. 즉, 거꾸로 최대공약수를 찾고 최대공약수와 그의 약수들을 구하면 끝이다.

 

추가로 A1 - A2 가 음수가 나올 수도 있기 때문에 정렬을 했다. 정렬을 하지 않고 A1 - A2 의 절댓값을 사용하도 무방하다.

 

전체 코드

import java.io.*;
import java.util.*;

public class Main_bj_2981_검문 {

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("res/input_bj_2981.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[] numbers = new int[N];
		
		for(int i=0; i<N; i++) {
			numbers[i] = Integer.parseInt(br.readLine());
		}
		
		Arrays.sort(numbers);
		
		StringBuilder sb = new StringBuilder();
		
		// 최대 공약수 구하기
		int gcd=0;
		for(int i=1; i<N; i++) {
			gcd = gcd(gcd, numbers[i]-numbers[i-1]);
		}
		
		
		// 최대 공약수의 약수 구하기
		for(int i=2; i<=gcd; i++) {
			if(gcd%i==0) {
				sb.append(i).append(" ");
			}
		}
		
		System.out.print(sb.toString());
		br.close();
	}
	
	static int gcd(int a, int b) {
		while(b!=0) {
			int r = a % b;
			a = b;
			b = r;
		}
		
		return a;
	}
}

 

---

Reference

https://st-lab.tistory.com/155

[백준] 2981번 : 검문 - JAVA [자바]