[백준 Baekjoon] 10818번 가로수 - JAVA

백준 Baekjoon 10818번 가로수 - JAVA

---

문제 풀이

문제의 예제 (1, 3, 7, 13) 에서 간격은 (2, 4, 6) 이고 2의 간격으로 가로수를 심으면 모든 가로수가 같은 간격으로 심어집니다. 다음 (2, 6, 12, 18)의 경우에도 (4, 6, 6) 이고 마찬가지로 2의 간격으로 가로수를 심습니다.

가로수를 같은 간격으로 심기 위해서는 가로수들의 간격의 최소공배수로 가로수를 심으면 됩니다. 앞에서부터 가로수 2개의 최소공배수를 구하고, 다음 가로수와 구한 최소공배수와의 최소공배수를 구하는 방법을 마지막까지 반복하여 최소공배수를 구합니다.

마지막 나무와 처음 나무의 차를 최소공배수로 나눠 총 몇그루의 나무가 심어지는지 구합니다. 다음 이미 심어져있는 나무의 개수 N을 빼준뒤 1을 더해 새로 심어야 하는 가로수 최소수를 구할 수 있습니다.

소스 코드

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

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

        int N = Integer.parseInt(br.readLine());

        int[] trees = new int[N];
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(br.readLine());
        }

        int gcd = 0;
        for (int i = 0; i < N - 1; i++) {
            int gap = trees[i + 1] - trees[i];
            gcd = gcd(gap, gcd);
        }

        System.out.println((trees[N - 1] - trees[0]) / gcd - N + 1);
    }

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