[백준] 2485번 - 가로수 [Java][C++]

문제 링크

---

1. 문제 풀이

모든 가로수가 같은 간격이 되도록 심어야 하는 가로수의 최소 개수를 구하는 문제로 주어진 입력에서 이웃한 가로수들의 간격들에 대한 최대공약수를 간격으로 설정하면 같은 간격이면서 가로수를 최소로 심을 수 있다.

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

---

2. 코드

1. 유클리드 호제법 [Java]

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 gcd = gcd(arr[1] - arr[0], arr[2] - arr[1]);
        for (int i = 3; i < N; i++) {
            gcd = gcd(gcd, arr[i] - arr[i - 1]);
        }

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

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

2. 유클리드 호제법 [C++]

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

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

    int n;
    cin >> n;

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

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

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

---

3. 풀이 정보

1. 유클리드 호제법 [Java]

언어	시간	메모리	코드 길이
Java 11	216 ms	23308 KB	701 B

2. 유클리드 호제법 [C++]

언어	시간	메모리	코드 길이
C++ 17	12 ms	2412 KB	362 B

---