[BaekJoon] #2485 - 가로수 [Java][C++]

문제 링크

---

1. 아이디어

모든 가로수가 같은 간격이 되도록 심어야 하는 가로수의 최소 개수를 구하는 문제로 주어진 입력에서 서로 이웃한 가로수들의 간격들에 대한 최대공약수를 최종 간격으로 설정하면 같은 간격이면서 가로수를 최소로 심을 수 있다. 추가되는 나무는 기존 나무 사이에만 심을 수 있어 기존 가로수의 위치가 그대로이므로 최종 간격은 모든 간격의 약수여야 하고, 간격이 클수록 심는 나무가 적으므로 그중 가장 큰 최대공약수가 답이 된다.

먼저 첫 번째 가로수와 두 번째 가로수 사이의 간격을 최대공약수로 초기화했다. 이후 다음 간격과 현재 구한 최대공약수와의 최대공약수를 구하는 과정을 반복하면 모든 이웃한 가로수 사이의 간격에 대한 최대공약수를 구할 수 있다. 해당 간격에 대해 필요한 가로수의 수는 시작 위치($\text{start}$), 끝 위치($\text{end}$), 간격($\text{dist}$)에 대해 $\dfrac{\text{end} - \text{start}}{\text{dist}} + 1$인데 이미 $N$개가 심어져 있으므로 이를 뺀 개수의 가로수만 심으면 된다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N \log M)$	$O(N)$

($N$ = 입력값 n, $M$ = 가로수 위치의 최댓값)

---

3. 코드

풀이 [Java][C++]

import java.io.*;

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];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        int g = arr[1] - arr[0];
        for (int i = 2; i < n; i++) {
            g = gcd(g, arr[i] - arr[i - 1]);
        }

        System.out.println((arr[n - 1] - arr[0]) / g + 1 - n);
    }

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<int> v(n);
    for (int& x : v) cin >> x;

    int g = v[1] - v[0];
    for (int i = 2; i < n; i++) {
        g = gcd(g, v[i] - v[i - 1]);
    }

    cout << (v[n - 1] - v[0]) / g + 1 - n;
}

---