[BOJ 2485] 가로수 (Java)

문제

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

2485번: 가로수

 

풀이

가로수 사이의 간격을 계산하여 저장한 후 , 간격들의 최대 공약수를 구한다. 

가로수의 최대 거리와 가로수의 최소 거리의 차이를 구한 후 최대 공약수로 나눠준다. (유클리드 호제법 사용)

양 끝이 모두 포함되므로, 나눈 값에 1을 더한 값이 가로수의 개수가 된다. 

이 개수에서 이미 심어져 있는 가로수 개수를 뺀 값이 정답이 된다.

 

소스코드

package math;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ2485 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];

        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(br.readLine());
            min = Math.min(arr[i], min);
            max = Math.max(arr[i], max);
        }
        int[] interval = new int[N-1];
        for(int i = 0; i < N-1; i++){
            interval[i] = arr[i+1] - arr[i];
        }

        int gcd = getGCD(interval[0], interval[1]);
        for(int i = 2; i < N-1; i++){
            gcd = getGCD(gcd, interval[i]);
        }

        System.out.println(((max-min)/gcd)+1 - (arr.length));
    }

    public static int getGCD(int a, int b){
        // great common divisor
        if(a < b){
            int temp = b;
            b = a;
            a = temp;
        }

        while(b != 0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

}