[백준] 17087번 숨박꼭질 6 JAVA

문제

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = reader.readLine().split(" ");
        int friend = Integer.parseInt(input[0]);
        int startPoint = Integer.parseInt(input[1]);
        String[] temp = reader.readLine().split(" ");
        int[] location = new int[temp.length+1];

//         시작점 + 친구들 위치
        location[0] = startPoint;
        for(int i=0; i< temp.length; i++){
            location[i+1] = Integer.parseInt(temp[i]);
        }
//        각 친구들 위치 사이 거리 배열
        int[] distance = new int[location.length-1];
        for(int i=0; i< location.length-1; i++){
            distance[i] = Math.abs(location[i] - location[i+1]);
        }
        int gcd = 0;
//        친구가 한명이면 둘 사이 거리 출력
        if(friend == 1){
            gcd = Math.abs(distance[0]);
        }else{
            gcd = getGcd(Math.max(distance[0], distance[1]), Math.min(distance[0], distance[1]));
            // 거리 배열의 최대공약수를 구한다
            for(int i=2; i<distance.length; i++){
                gcd = getGcd(Math.max(gcd, distance[i]), Math.min(gcd, distance[i]));
            }
        }
        writer.append(Integer.toString(gcd));
        writer.append("\n");

        reader.close();
        writer.flush();
    }

    public static int getGcd(int big, int small){
        int remain = big%small;
        if(remain !=0){
            return getGcd(small, remain);
        }else {
            return small;
        }
    }
}

여러 수의 최대공약수는

앞에서부터 순차적으로 최대공약수를 구하고

그 최대공약수와 다음 수와 최대공약수를 또 구하는 방식으로 구현하면 된다.

 

예를 들면

입력 => 24 36 70

24와 36의 최대공약수는 12

12와 다음수인 70의 최대공약수는 2

세 수의 공통 최대 공약수는 2가 된다.