[P&B] #99 BAEKJOON 2485

백준 2485번 가로수 JAVA

문제 설명

직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.

편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.

예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.

심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 되도록 새로 심어야 하는 가로수의 최소수를 구하는 프로그램을 작성하라. 단, 추가되는 나무는 기존의 나무들 사이에만 심을 수 있다.

 

입력

첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가로수의 위치를 나타내는 정수는 1,000,000,000 이하이다. 가로수의 위치를 나타내는 정수는 모두 다르고, N개의 가로수는 기준점으로부터 떨어진 거리가 가까운 순서대로 주어진다.

 

출력

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

 

나의 문제 풀이 코드

import java.io.*;
import java.util.*;

public class bj2485 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        long[] tree = new long[N];
        for (int i = 0; i < N; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        Arrays.sort(tree);
        long minGap = findMinGap(tree);
        long count = 0;
        for (int i = 1; i < N; i++) {
            count += (tree[i] - tree[i - 1]) / minGap - 1;
        }
        bw.write(String.valueOf(count));
        bw.close();
    }

    private static long findMinGap(long[] arr) {
        long minGap = arr[1] - arr[0];
        for (int i = 2; i < arr.length; i++) {
            minGap = gcd(minGap, arr[i] - arr[i - 1]);
        }
        return minGap;
    }

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

 

문제 풀이 코멘트

이 문제는 각각 위치해있는 가로수들의 간격 차이를 구하여 간격들의 최대 공약수를 구하면 그 수가 같은 간격이 되는 가로수의 간격이 되는 것이고 그 것을 이용해 심어야하는 나무의 수를 구하는 문제였습니다.

먼저 입력받은 가로수의 위치가 오름차순이 아닌 경우를 고려해 정렬을 한 뒤 findMinGap으로 가로수 간격의 최소 공약수를 찾습니다. 이 함수는 가로수 위치 배열을 입력으로 받아 최소 공약수를 계산합니다.

gcd(minGap, arr[i] - arr[i - 1])를 좀 더 설명하자면, minGap 변수는 초기에 첫 번째 가로수와 두 번째 가로수 간의 간격 차이로 초기화됩니다.이후 for 루프를 통해 가로수 배열을 순회하면서 현재 간격 차이(arr[i] - arr[i - 1])와 minGap의 GCD를 계산합니다. GCD는 두 수의 최대 공통 약수를 의미하는데, 현재 간격 차이와 이전까지의 최소 공약수(GCD)를 계산함으로써, 모든 간격 차이의 공통된 약수를 찾아낼 수 있습니다.

최적의 간격을 구하면 가로수 배열을 순회하면서 각 가로수 간의 차이를 계산하고, 최소 공약수로 나누어 추가로 필요한 가로수 개수를 계산합니다. 이렇게 계산된 개수를 count에 누적합니다.

count += (tree[i] - tree[i - 1]) / minGap - 1로 count를 갱신하는데 현재 가로수와 이전 가로수 간의 간격 차이를 계산하여  그 값을 minGap으로 나누면 현재 간격을 최소 공약수(GCD)로 나눈 횟수를 구할 수 있습니다. 그리고 현재 간격을 최소 공약수로 나눈 결과에서 1을 빼면 추가로 필요한 가로수의 개수를 나타냅니다

최대 공약수는 유클리드 호제법(https://mingming0o0.tistory.com/85)을 사용하여 계산했습니다.