백준 [17087] 숨바꼭질 6 (자바)

문제

• 풀이
• 수빈이의 지점과 모든 동생의 위치 사이의 거리를 구한다.
• 각 위치들의 최대 공약수를 구한다. (유클리드 호제법 사용)
• 유클리드 호제법
  • 나머지가 0이 되어 더이상 나누어질 수 없을 때까지 반복해서 나누어 최대 공약수를 구하는 방법
• 모든 동생위치에 대한 최대 공약수를 구해준다.

정답코드

package com.baekjoon.p17087;

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        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] = Math.abs(Integer.parseInt(st.nextToken()) - s); // s와 거리 구하기
        }

        int d = arr[0];

        /**
         * 모든 배열을 돌면서 최대공약수를 구하고 구한 공약수와 다음 배열의 수의 최대 공약수 구하기
         */
        for (int i = 0; i < n; i++) {
            d = gcd(d, arr[i]);
        }

        System.out.println(d);
    }

    static int gcd(int a, int b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
}