[백준] 2485. 가로수

문제 링크

[백준] 2485. 가로수

풀이 과정

먼저, 가로수를 최소로 추가하기 위한 가로수 사이의 간격 기준을 정하는 작업부터 알아보겠습니다.

가로수가 2, 4, 7 위치에 심어져 있다면, 그 간격은 각각 2와 3이 되며, 최소 간격은 그보다 작은 1 이 됩니다.

가로수가 1, 3, 7, 13 위치에 심어져 있다면, 그 간격은 각각 2, 4, 6이 되며, 최소 간격은 2 가 됩니다.

따라서, 다음과 같은 아이디어를 낼 수 있습니다.

1. 최소 갯수로 가로수를 심어, 인접한 둘 간의 간격이 같기 위해서는 그 간격이 이미 심어져 있는 가로수들의 간격들의 최소 공약수 가 되어야 한다.
2. 이미 심어져 있는 가로수들 사이의 간격을 최소 공약수로 나눈 후 1을 빼면, 각 간격에서 추가로 심어야 하는 가로수들의 개수가 나온다.

코드

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

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[] arr = new int[N];
        int gcd = 0;
        int answer = 0;

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

        Arrays.sort(arr);

        for (int i = 0; i < N - 1; i++) {
            int gap = arr[i + 1] - arr[i];
            gcd = GCD(Math.max(gcd, gap), Math.min(gcd, gap));
        }

        for (int i = 0; i < N - 1; i++) {
            int gap = arr[i + 1] - arr[i];
            answer += gap / gcd - 1;
        }

        System.out.println(answer);
    }

    static int GCD(int a, int b) {
        return b == 0 ? a : GCD(b, a % b);
    }
}