[Java] 백준 2110번 공유기 설치

이분 탐색 문제입니다.

N개의 집에 C개의 공유기를 설치하여 인접한 두 공유기 사이의 최대로 하여야 합니다.

먼저 정렬을 해주어서 공유기의 위치를 차례대로 나열해줍니다.
인접한 공유기와 거리를 배열에 저장합니다.
이분 탐색을 통해 0~1,000,000,000의 값들 중 가능한 값들을 찾아나갑니다.

1. 가능 한 경우
더 높은 경우가 있는지 확인하기 위해서
left = mid + 1

2. 불가능 한 경우
가능한 경우를 찾기 위해서
right = mid - 1

위의 과정을 left > right가 될 때까지 반복해줍니다.
위의 과정에서 가장 큰 값을 출력해줍니다.

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

public class Main {
  static int result;
  static int n;
  static int c;
  static int[] arr;
  static int[] dist;

  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    result = 0;
    n = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());
    arr = new int[n];
    dist = new int[n];

    arr[0] = Integer.parseInt(br.readLine());
    for (int i = 1; i < n; ++i) {
      arr[i] = Integer.parseInt(br.readLine());
    }

    Arrays.sort(arr);

    for (int i = 1; i < n; ++i) {
      dist[i] = arr[i] - arr[i - 1];
    }

    int left = 1;
    int right = 1_000_000_000;
    while (left <= right) {
      int mid = (left + right) / 2;
      System.out.println(left + " " + right + " " + mid);
      if (search(1, 0, 1, mid)) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    bw.write(result + "\n");
    bw.close();
  }

  public static boolean search(int index, int prev, int cnt, int num) {
    if (cnt == c) {
      result = Math.max(result, num);
      return true;
    }

    if (index == n) {
      return false;
    }

    if (dist[index] + prev >= num) {
      return search(index + 1, 0, cnt + 1, num);
    } else {
      return search(index + 1, prev + dist[index], cnt, num);
    }
  }
}