[백준] 2110 : 공유기 설치 - Java

• 백준 문제 URL

집 n개에 공유기 c개를 설치해 최소 거리 최대화하는 문제
집 위치가 주어질 때, 공유기 c개를 설치하여 인접 공유기 간 최소 거리를 최대화함.

---

문제 접근

• 입력
  첫 줄에 n c (2 ≤ c ≤ n ≤ 200,000)
  다음 n줄에 집 위치 (1 ≤ x ≤ 10^9)

  예를 들어,

  5 3
  1
  2
  4
  8
  9

  입력 시, 최대 최소 거리 3이 됨.

• 출력
  공유기 c개를 설치했을 때 최대화된 최소 거리를 출력함.

---

제출

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

// 공유기 설치
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 집 수
        int c = Integer.parseInt(st.nextToken()); // 공유기 수

        int[] addressArr = new int[n];
        for (int i = 0; i < n; i++) {
            int address = Integer.parseInt(br.readLine()); // 집 번지
            addressArr[i] = address;
        }
        Arrays.sort(addressArr);

        int left = 1; // 최소거리 하한 (1)
        int right = addressArr[n - 1] - addressArr[0]; // 최대거리 상한
        int answer = 0;

        while (left <= right) {
            int mid = (left + right) / 2;  // 최소거리 후보

            // mid 거리로 공유기 몇 개 설치 가능한지 확인
            int count = getCount(addressArr, mid);  // 설치 가능한 공유기 수

            if (count >= c) {  // c개 이상 설치 가능
                answer = mid;    // 가능한 최대 거리 갱신
                left = mid + 1;  // 더 큰 거리 시도
            } else {
                right = mid - 1; // 거리 줄여야 함
            }
        }
        System.out.println(answer);
    }

    // mid 거리로 공유기 몇 개 설치 가능한지 계산
    static int getCount(int[] arr, int dist) {
        int count = 1;  // 첫번째 집에 설치
        int last = arr[0];  // 마지막 설치 위치

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] - last >= dist) {  // dist 이상 떨어졌으면 설치
                count++;
                last = arr[i];
            }
        }
        return count;
    }
}

---

핵심 개념

1. 파라메트릭 서치(Parametric Search)
   최소 거리 D를 이분탐색으로 찾음.
   "거리 D로 공유기 c개 설치 가능한가?" → 가능하면 D↑, 불가능하면 D↓.

2. getCount() 핵심 로직

   count=1, last=첫집
   for(다른집들):
       집-last >= dist → count++, last=집
   return count

3. 이분탐색 범위

   • left = 1: 가장 작은 가능 거리
   • right = 마지막집-첫집: 가장 큰 가능 거리

4. 시간복잡도

   • 정렬: O(n log n)
   • 이분탐색: O(log 10^9) × getCount O(n)
   • 총 O(n log n) — n=2×10^5 통과 보장.

---

출력 예시

입력

5 3
1
2
4
8
9

출력

3

계산 과정:

집 정렬: [1,2,4,8,9]
1. mid=4 → 설치: 1,8 → count=2 <3 → right=3
2. mid=2 → 설치: 1,4,8 → count=3 >=3 → answer=2, left=3  
3. mid=3 → 설치: 1,4,9 → count=3 >=3 → answer=3, left=4
4. mid=4 → count=2 <3 → right=3
5. left=4 > right=3 → answer=3 ✓

---

흔한 실수와 해결

❌ 실수	✅ 해결
int c 대신 int m	문제에서 c(공유기 수)
getCount() 누락	별도 함수로 구현
left=0	left=1 (거리 0 의미없음)
mid = left + (right-left)/2	(left+right)/2도 충분히 안전

---

정리

• 파라메트릭 서치 패턴
• `"거리 D로 c개 설치 가능한가?" 판단 필요
• 정렬 → 이분탐색 → getCount