[백준 2110] 공유기 설치
사용 알고리즘 : 이분 탐색, 매개 변수 탐색(Parametric Search)
📚 문제
🔗 문제 링크
📖 문제 설명
- 수직선 위에 N개의 집이 있음
- 각 집의 좌표는 서로 다름
- C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하려고 함
- 가장 인접한 두 공유기 사이의 최대 거리를 구해야 함
🔍 입력 조건
- 첫째 줄에 집의 개수 N과 공유기의 개수 C가 주어짐 (2 ≤ N ≤ 200,000, 2 ≤ C ≤ N)
- 둘째 줄부터 N개의 줄에 집의 좌표가 하나씩 주어짐 (0 ≤ 좌표 ≤ 1,000,000,000)
🔍 출력 조건
- 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력
🧩 문제 분류
- 알고리즘: 이분 탐색, 매개 변수 탐색(Parametric Search)
- 자료구조: 배열
- 난이도: Gold IV
🚀 접근 방법
- 집의 좌표를 오름차순으로 정렬
- 가능한 공유기 간 거리의 범위를 설정 (1 ~ 가장 먼 두 집 사이의 거리)
- 이분 탐색을 사용하여 최적의 거리를 찾음
- 각 거리로 설치했을 때 설치 가능한 공유기의 개수를 계산
- C개 이상 설치 가능하면 거리를 늘리고, C개 미만이면 거리를 줄임
💻 구현
package baekjoon.binarysearch.gold;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ2110 {
private static final int MAX_DISTANCE = 1000000000; // 공유기 간 최대 거리
static int N, C;
static int[] houses;
public static int getMaxDistance(int s, int e){
int answer = 0;
while(s <= e){
int mid = (s + e) / 2; // 공유기 간의 거리.
int cnt = 1;
int lastHouse = houses[0];
for (int i = 1; i < N; i++){
// 이전 공유기와의 거리가 mid 이상이면 설치.
if (houses[i] - lastHouse >= mid){
cnt++;
lastHouse = houses[i];
}
}
if (cnt >= C){
answer = mid;
s = mid + 1;
}
else{
e = mid - 1;
}
}
return answer;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
houses = new int[N];
for (int i = 0; i < N; i++){
houses[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(houses);
System.out.println(getMaxDistance(1, MAX_DISTANCE));
}
}
⏱ 시간 복잡도
- O(N log N + N log X), 여기서 X는 최대 좌표값
- 정렬: O(N log N)
- 이분 탐색: O(log X)
- 각 단계에서 모든 집 확인: O(N)
💾 공간 복잡도
- O(N): 집의 좌표를 저장하는 배열의 크기
🧪 테스트 케이스
| 입력 | 출력 |
|---|---|
| 5 3 1 2 8 4 9 | 3 |
📝 회고
- 이분 탐색 유형이라는 것을 알았음에도 어떻게 이분 탐색을 사용해야 할 지가 어려웠음.
- 문제 풀이는 쉬우나 최적화 문제를 결정 문제로 나눠서 푼다는 감을 익히는 게 좋을 듯.
- Parametic Search에 대해 한번 찾아보게 됨.
