[Java] BOJ 2981번 검문

2981번: 검문

---

풀이

유클리드 호제법을 사용하여 해결했습니다.

수학과 관련된 알고리즘에 대해 부족함을 많이 느낄 수 있었던 문제였습니다.

정말 정리가 잘 된 블로그가 있어 링크를 남깁니다.

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

---

코드

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

public class Main {
	public static int N;
	public static int[] num;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		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 = getGcd(gcd, num[i] - num[i - 1]);
		}
		
		StringBuilder sb = new StringBuilder("");		
		for (int i = 2; i <= gcd; ++i) {
			if (gcd % i == 0) {
				sb.append(i).append(" ");
			}
		}
		
		System.out.println(sb);
	}
	
	// 유클리드 호제법
	public static int getGcd(int n1, int n2) {
		while (n2 != 0) {
			int r = n1 % n2;
			n1 = n2;
			n2 = r;
		}
		
		return n1;
	}
}

---

pyo7410/Algorithm