[JAVA] 백준 17087번- 숨바꼭질 6

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

17087번: 숨바꼭질 6

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());

        ArrayList<Integer> list = new ArrayList<>();

        while(n-->0){
           list.add(Math.abs(s - Integer.parseInt(st.nextToken())));
        }
        int answer = list.get(0);
        for(int x : list){
            answer = gcd(answer, x);
        }
        System.out.println(answer);
    }
}

 

 

수빈이와 동생들 사이의 각각의 거리들의 최대공약수를 구하면 된다.

유클리드 호제법을 이용해 최대공약수를 구하는 gcd 함수를 만들고,

거리가 담겨있는 리스트를 하나씩 돌며 최대공약수를 갱신해줬다.