백준 / 17087 숨바꼭질6

문제

풀이

설명

수빈이와 동생 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