[백준 문제 풀이] 2485번 가로수

Junu Kim·2026년 1월 3일

Java baekjoon boj

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

81/89

[2485] 가로수

난이도: ★★★☆☆ • solved on: 2026-01-03

문제 요약

문제 유형: 수학, 최대공약수(GCD)
요구사항: 기존 가로수 위치를 기준으로 모든 가로수 사이의 간격이 동일해지도록 만들 때, 추가로 심어야 하는 가로수의 개수를 구해야 한다.

사용 개념

자료구조
- long[] : 가로수 좌표 및 간격 저장
알고리즘/기법
- 정렬
- 유클리드 호제법 (Euclidean Algorithm)
핵심 키워드
- 인접 간격
- 간격들의 최대공약수 (GCD)
- (gap / gcd) - 1

풀이 아이디어 및 코드

방법 1 : 현재 가로수의 위치 정보를 저장

문제 분해

가로수 위치를 배열에 저장한다.

인접한 가로수 사이의 간격 배열 gaps를 만든다.

모든 간격의 GCD를 구해 currentGcd로 저장한다.

첫 위치부터 마지막 위치까지 currentGcd 간격으로 하나씩 훑으면서,
기존 가로수가 없는 위치를 카운트한다.
핵심 로직 흐름
gaps 생성
gaps 전체 GCD 계산 → currentGcd
start부터 end까지 currentGcd 간격으로 순회
    기존 위치에 없으면 count++
3. **한계**

   * 좌표 범위가 커질 경우, while 문 순회 횟수가 불필요하게 많아질 수 있다.
   * 실제로는 계산으로 바로 구할 수 있는 값을 시뮬레이션으로 처리하고 있다.

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] positions = new long[n];
        long[] gaps = new long[n-1];
        long currentGcd = 1;

        for(int i=0;i<n;i++){
            positions[i] = Long.parseLong(br.readLine());
            if(i > 0){
                gaps[i-1] = positions[i] - positions[i-1];
            }
            if(i == n-1){
                break;
            }
        }

        Arrays.sort(positions);

        for(int i=0;i<n-1;i++){
            if(i == 1){
                currentGcd = gcd(gaps[i-1], gaps[i]);
            } else if (i > 1){
                currentGcd = gcd(currentGcd, gaps[i]);
            }
        }

        int i = 0;
        int j = 0;
        long start = positions[0];
        int count = 0;

        while((start + currentGcd * j) <= positions[positions.length-1]){
            if(positions[i] == start + currentGcd * j){
                i ++;
                j ++;
                continue;
            } else {
                count++;
                j ++;
            }
        }
        System.out.println(count);
    }

    public static long gcd(long a,long b){
        while(b != 0){
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

방법 2 : 위치 정보 대신 간격 합산에 집중

핵심 관찰

최종적으로 모든 가로수 사이의 간격은
“인접 간격들의 최대공약수(GCD)”가 된다.
계산 방식

어떤 간격 gap이 있고 최종 간격이 gcd라면,

해당 구간은 gap / gcd개의 구간으로 나뉜다.

이미 양 끝에 나무가 있으므로, 추가로 필요한 나무 수는 (gap / gcd) - 1이다.

전체 답

모든 인접 간격에 대해 위 값을 더한 합이다.
핵심 로직 흐름
positions 정렬
모든 인접 gap의 GCD 계산 → g
answer = Σ (gap / g - 1)

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

class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = a % b;
            a = b;
            b = t;
        }
        return a;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long[] pos = new long[N];
        for (int i = 0; i < N; i++) {
            pos[i] = Long.parseLong(br.readLine());
        }

        Arrays.sort(pos);

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

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

        System.out.println(answer);
    }
}

시간·공간 복잡도

방법 1

시간 복잡도: $O(N log N + R / G)$ (R: 좌표 범위, G: 최종 간격)
공간 복잡도: $O(N)$

방법 2

시간 복잡도: $O(N log N)$
공간 복잡도: $O(N)$

어려웠던 점

구현 자체는 단순했지만, 시뮬레이션을 수식으로 치환할 수 있다는 발상에 도달하기 어려웠다.
“모든 위치를 직접 세어보지 않아도 된다”는 점을 떠올리지 못해 시간복잡도 개선 방향을 잡는 데 시간이 걸렸다.

배운 점 및 팁

동일 간격을 만드는 문제는 대부분 간격들의 GCD로 귀결된다.
좌표 문제에서 “하나씩 훑는 방식”이 보이면, 간격 단위로 계산할 수 있는지 먼저 의심해보는 것이 좋다. (위치 정보의 필요성에 대한 의심)
추가 개수는 시뮬레이션보다
$Σ (gap / gcd - 1)$ 형태의 수식이 훨씬 안전하고 빠르다.