수빈이와 동생 N명이 있다.
수빈이는 동생 N명을 거쳐 마지막 동생까지 찾아야하고 수빈이는 걷거나 순간이동을 할 수 있다.
수빈이의 위치가 X일 때 걷는다면 1초 후에 X-D 또는 X+D로 이동할 수 있다.
수빈이가 모든 동생을 거쳐서 찾아가기 위한 D의 최댓값을 구하여야 한다.
X -> Y로 이동하는 경우 (X < Y)
X -> X+D 또는 X-D로만 이동하려면 Y-D가 D의 배수가 되어야 한다.
X -> Y,Z로 이동하는 경우는 (X < Y, X < Z)
X -> X+D 또는 X-D로만 이동하려면 Y-X가 D의 배수가 되어야 하고, Z-X가 D의 배수가 되어야 한다.
즉 D는 수빈이와 동생 거리차이(|A1-X|,|A2-X|)의 약수임을 알 수 있다 그리고 D의 최대값은 최대 공약수를 구하는 것이라 볼 수 있다.
import java.util.*;
public class Num17087 {
// 유클리드 호재법을 통해 최대공약수를 리턴
private static int gcd(int x, int y) {
if (y == 0) {
return x;
} else {
return gcd(y, x%y);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 동생 수
int s = sc.nextInt(); // 수빈이 현재 위치
int[] a = new int[n]; // 동생들과 수빈이 거리 차이 배열
for (int i = 0; i<n; i++) {
int x = sc.nextInt(); // 수빈이가 동생들을 만나는 위치
int diff = Math.abs(x-s); // 거리차이를 구하기 위해 절대값 반환
a[i] = diff; // 수빈이와 동생들의 거리 차이를 배열에 저장
}
int ans = a[0];
for(int i = 1; i<n; i++) {
ans = gcd(ans, a[i]);
}
System.out.println(ans);
}
}
참고 : 백준 코드플러스
출처 : https://www.acmicpc.net/problem/17087