[BOJ 2981번] 검문(JAVA)

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

2981번: 검문

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

public class Main {
	static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
	static StringBuilder sb=new StringBuilder();
	static long[] number;
	
	public static void main(String args[]) throws Exception {
		int num=Integer.parseInt(br.readLine());
		number=new long[num];
		for(int i=0;i<num;i++) {
			number[i]=Integer.parseInt(br.readLine());
		}
		Arrays.sort(number);
		long result=number[1]-number[0];
		for(int i=2;i<num;i++) {
			result=getGCD(Math.max(result, number[i]-number[i-1]), Math.min(result, number[i]-number[i-1]));
		}
		
		for(int i=2;i<=result/2;i++) {
			if(result%i==0) sb.append(i+" ");
		}
		sb.append(result);
		System.out.println(sb);
	}
	public static long getGCD(long a, long b) {
		while (b > 0)
	    {
	        long tmp = a;
	        a = b;
	        b = tmp%b;
	    }
	    return a;
	}
}

이 문제는 점화식을 구해서 풀어야하는 문제였습니다.

저는 아래 블로그를 참조하여 문제를 풀 수 있었습니다.

https://pangsblog.tistory.com/62

[백준 2981] - [수학 최대공약수] - 검문 (JAVA)

저는 number 배열을 선언했는데요, 이 배열 값들을 M으로 나누는 상황을 살펴봅시다.

배열이 N번째 인덱스까지 있다고 한다면, 

number[1]%M=number[1]-(number[1]/M)*M;

number[2]%M=number[2]-(number[2]/M)*M;

number[3]%M=number[3]-(number[3]/M)*M;

...

number[N]%M=number[N]-(number[N]/M)*M

임의의 정수 i에 대하여 number[i]%M 값은 모두 같습니다.

이 식들을 서로 빼보면

number[i]-(number[i]/M)*M=number[i+1]-(number[i+1]/M)*M

따라서 number[i+1]-number[i]=M*(number[N-1]/M-number[N]/M)

 

이러한 점화식을 구할 수 있는데요, 이 점화식을 통해 알 수 있는 것은 수들이 같은 나머지를 가질 때 i번째 수에서 i-1번째 수를 빼면 공통된 M 값을 가진다는 것을 알 수 있고, 이 M 값은 number[i]-number[i-1]의 약수라는 것을 알 수 있습니다.

따라서 number[1]-number[0]부터 number[i]-number[i-1]까지의 공약수를 구하면 됩니다.