[JAVA] 백준 2981번 : 검문

 

---

 

• 생각

처음 풀어보니 시간초과가 떴다. 다른 사람이 잘 정리해놓은 것을 가져왔다. (링크)

 

문제에서 매우매우 중요한 키워드가 두 개 있다.

첫 번째로 'M이 하나 이상 존재하는 경우로만 주어진다' 이다.

두 번째로 '나머지가 모두 같게 되는 M을 찾으려고 한다' 이다.

 

이 두 문장을 잘 생각해보면 다음과 같다. '나머지가 같은 경우는 반드시 존재하며 이 때의 M은 모든 수에서 동일하다.'

그러면 모든 수에서 '동일하다'라는 의미는 결과적으로 M은 공약수라는 말 아니겠는가?

 

즉, 위 문제의 예제로 보면 이렇다는 것이다.

6 / M + r

34 / M + r

38 / M + r

 

여기서 r은 모두 같다는점. 즉, r만 0으로 만들 수 있다면 M을 쉽게 구할 수 있다는 것이다. 

 

(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)의 공약수라는 의미라는 것.

 

 

만약 다른 예제로 17, 34, 24, 52, 39 가 있으면,

(17 - 34)와 (34 - 24)와 (24 - 52)와 (52 - 39)의 공약수를 찾으면 된다는 것이다.

 

 

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

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

 

• 코드

정답 코드 : 유클리드 호제법을 이용하여 구현했다.

 

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

public class Main {
	static int N, M;
	static StringBuilder sb;

	public static void main(String[] args) throws Exception {
		SetData();
		System.out.println(sb);
	}

	private static void SetData() throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		sb = new StringBuilder();
		int[] array = new int[N];	
		
		for(int i = 0; i < N ; i++) 
			array[i] = Integer.parseInt(br.readLine());
		 
		Arrays.sort(array);		 
		int gcdValue = array[1] - array[0];	// 음수가 되지 않도록 큰 수에서 작은 수로 빼줌
	 
		for(int i = 2; i < N; i++) {
			// 직전의 최대 공약수와 다음 수(array[i] - array[i - 1])의 최대공약수를 갱신 
			gcdValue = getGCD(gcdValue, array[i] - array[i - 1]);
		}
	
		for(int i = 2; i <= gcdValue; i++) {
			// i가 최대공약수의 약수라면 출력
			if(gcdValue% i == 0) {
				sb.append(i + " ");
			}
		}
	}

	private static int getGCD(int p, int q) {
		if (q == 0) {
			return p;
		}
		return getGCD(q, p % q);
	}

}