이진탐색 공유기설치

파라메트릭 서치를 활용한 문제다. GAP을 이용해야한다.

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());
    ArrayList<Integer> list = new ArrayList<>();
    for (int i = 0; i < N; i++) list.add(Integer.parseInt(br.readLine()));

    Collections.sort(list);

    int start = 1; // 가능한 최소 거리 (min gap)
    int end = list.get(N - 1) - list.get(0); // 가능한 최대 거리 (max gap)
    int answer = 0;
    
    while (start <= end) {
      int mid = (start + end) / 2;  // mid는 가장 인접한 두 공유기 사이의 거리(gap)을 의미
      int value = list.get(0); // 첫째 집에는 무조건 공유기를 설치한다고 가정

      int count = 1;
      
      // 현재의 mid값을 이용해 공유기를 설치하기
      for (int i = 1; i < N; i++) {
        if (list.get(i) >= value + mid) {
          value = list.get(i);
          count += 1;
        }
      }

      // C 개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가
      if (count >= C) {
        start = mid + 1;
        answer = mid; // 최적의 결과 저장

      // C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소시키기
      } else { 
        end = mid - 1;
      }
    }
    System.out.println(answer);
  }
}