[BOJ] 17087 숨바꼭질 6 - JAVA

1. 문제

17087번: 숨바꼭질 6

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

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

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

---

2. 풀이

점끼리의 간격을 구해서, 그 간격들의 최대공약수를 구하면 된다. (설명을 더 잘 하고 싶었는데 못하겠다..)

S까지 A 배열에 넣어서 같이 계산했다.

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

public class BOJ_17087_숨바꼭질6 {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(in.readLine());
      int N = Integer.parseInt(st.nextToken());
      int[] A = new int[N+1];
      A[0] = Integer.parseInt(st.nextToken());

      st = new StringTokenizer(in.readLine());
      for(int i=1;i<=N;i++) {
         A[i] = Integer.parseInt(st.nextToken());
      }

      int answer = Math.abs(A[0]-A[1]);
      for(int i=2;i<=N;i++) answer = gcd(answer, Math.abs(A[i]-A[i-1]));

      System.out.println(answer);
   }
   public static int gcd(int a, int b){
      if(a<b){
         int tmp = a;
         a = b;
         b = tmp;
      }
      if(b==0) return a;
      return gcd(b,a%b);
   }
}

---

3. 결과