문제
N개의 집 좌표가 주어질 때 C개의 공유기를 설치하여, 인접한 공유기 간 최소 거리가 최대가 되도록 하는 문제다. 직접 모든 조합을 탐색하면 경우의 수가 너무 많으므로, "최소 거리가 d일 때 C개를 설치할 수 있는가"를 판별 함수로 만들고 d에 대해 이분 탐색(매개 변수 탐색)을 적용한다.
입력
- 첫째 줄: 집의 수 N (2 이상 200,000 이하), 공유기 수 C (2 이상 N 이하)
- 둘째 줄부터 N개 줄: 집의 좌표 (1 이상 1,000,000,000 이하)
출력
인접한 공유기 사이의 최소 거리의 최댓값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 1 2 8 4 9 | 3 |
풀이
집 좌표를 정렬한 뒤, 최소 거리 d를 이분 탐색으로 결정하는 매개 변수 탐색을 적용한다.
- 집 좌표 배열을 오름차순 정렬
- 탐색 범위:
lo=1,hi=arr[N-1]-arr[0]+1 mid = (lo+hi)/2로 후보 최소 거리 설정check(mid): 첫 집에 공유기를 놓고, 이전 설치 위치로부터 mid 이상 떨어진 곳에만 추가 설치하며 총 설치 가능 수를 반환check(mid) >= C이면 거리를 더 늘릴 수 있으므로lo=mid+1, 아니면hi=mid- 최종 답은
lo-1
핵심 아이디어: "최소 거리 d가 주어지면 몇 개 설치 가능한가"는 그리디(Greedy)로 O(N)에 판별되므로, 전체 탐색을 O(N log D)로 줄일 수 있다(D는 좌표 범위).
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Day120BOJ2110공유기설치BinarySearch기본 { // 2110 공유기 설치
static int N, M;
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] ss = br.readLine().split(" ");
N = Integer.parseInt(ss[0]);
M = Integer.parseInt(ss[1]);
arr = new int[N];
for (int i = 0; i < N; i++)
arr[i] = Integer.parseInt(br.readLine());
Arrays.sort(arr);
int lo = 1;
int hi = arr[N - 1] - arr[0] + 1;
while (lo < hi) {
int mid = (hi + lo) / 2;
if (check(mid) < M)
hi = mid;
else
lo = mid + 1;
}
System.out.println(lo - 1);
br.close();
}
private static int check(int d) {
int cnt = 1;
int last = arr[0];
for (int i = 1; i < arr.length; i++) {
int l = arr[i];
if (l - last >= d) {
cnt++;
last = l;
}
}
return cnt;
}
}복잡도
- 시간: O(N log D) — 정렬 O(N log N) + 이분 탐색 O(log D) × 판별 O(N), D는 좌표 최대 범위
- 공간: O(N) — 좌표 배열