[백준 온라인 저지] 2485. 가로수

1. 입력

- 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000).

- 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르다.

 

2. 출력

- 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 첫 번째 줄에 출력한다.

 

3. 코드

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(br.readLine());
        int a = Integer.valueOf(br.readLine());
        int[] num = new int[n-1];
        for(int i=0 ; i<n-1 ; i++){
            int b = Integer.valueOf(br.readLine());
            num[i] = b-a;
            a = b;
        }
        int gcd = num[0];
        for(int i=1 ; i<n-1 ; i++)
            gcd = findGCD(Math.max(gcd,num[i]), Math.min(gcd,num[i]));
        int answer = 0;
        for(int i=0 ; i<n-1 ; i++)
            answer += num[i]/gcd -1;
        System.out.print(answer);
    }
    static int findGCD(int a, int b){
        if(b==0) return a;
        return findGCD(b, a%b);
    }
}