[백준]2981번 검문(java)

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

2981번: 검문

백준 2981번 검문 문제 링크입니다.

 

핵심

여러 수를 받고 그 수들을 나누었을 때, 나머지가 같은 값이 나오게 하는 수를 찾는 것이다. 단순한 방법으로는 2부터 1씩 증가시키면서 값을 나누었을 때, 나머지를 비교하는 것이지만, 이러한 방법은 시간 초과가 뜨게 된다. 따라서 우리는 유클리드 호제법을 사용하여 문제를 풀어야 한다.

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

정답 코드

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+" ");
				
	}
}

 

해설

여러 가지 입력받은 수를 배열에 넣어준다. 이후 Arrays.sort를 사용하여 정렬을 한다.

이후 GCD라는 메서드에 첫 번째 값이 되는 배열 두 번째-배열 세 번째, 배열 세 번째-배열 두 번째 값을 넣어준다.

GCD에서는 b가 0이 될 때까지 GCD메서드를 다시 수행한다.배열 끝까지 메서드 GCD에 대입되면 gcd의 값은 최대 공약수가 된다.이후 최대 공약수의 약수들 중에서 2 이상의 값들을 출력하고, 최대공약수 자신을 출력한다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.