[Java/자바][백준17087: 숨바꼭질6]

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

17087번: 숨바꼭질 6

Problem

수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다.

수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이동할 수 있다. 수빈이의 위치가 동생이 있는 위치와 같으면, 동생을 찾았다고 한다.

모든 동생을 찾기위해 D의 값을 정하려고 한다. 가능한 D의 최댓값을 구해보자.

 

Input

첫째 줄에 N(1 ≤ N ≤ 105)과 S(1 ≤ S ≤ 109)가 주어진다. 둘째 줄에 동생의 위치 Ai(1 ≤ Ai ≤ 109)가 주어진다. 동생의 위치는 모두 다르며, 수빈이의 위치와 같지 않다.

 

Output

가능한 D값의 최댓값을 출력한다.

 

Insight

1. 수빈이의 위치에서 동생들의 위치에서 가기 위한 최대 D값은 최대 공약수로 결정할 수 있다. 

 ex) 수빈이 위치 3, 동생들의 위치 1, 7, 11  -> 수빈이의 위치에서 동생들의 위치를 가기 위해 필요한 값은 각각 |3-1|, |3-7|, |3-11| = 2, 4, 8 이다. 

하나의 값으로 모든 위치를 가기 위한 최대값은 2,4,8,의 최대 공약수 2가 된다.  

 

<Process> 
1. | S-A1 | 부터 | S-AN| 까지 반복문으로 최대공약수를 찾는다. 

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

public class Main {
	
	public static int GCD(int a, int b) {
		if(a==0) {return b;}
		else {
			return GCD(b%a, a); 
		}
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " "); 
		int N = Integer.parseInt(st.nextToken());
		int S = Integer.parseInt(st.nextToken());
		int[] arr = new int[N]; 
		
		st = new StringTokenizer(br.readLine(), " ");
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		int gcd = Math.abs(arr[0] - S); 
		
		if(S>1) {
			for(int i=1; i<N; i++) {
				gcd = GCD(gcd, Math.abs(arr[i]-S)); 
			}
		}
		bw.write(String.valueOf(gcd));
		
		bw.flush();
		bw.close();
	}
}