[JAVA] BOJ 백준 2110

https://www.acmicpc.net/problem/2110

문제

도현의 집 N개는 수직선상에 있다. 각 집의 좌표는 x1,…,xN이며 두 집의 좌표가 동일하지 않습니다.

도현은 언제 어디서나 Wi-Fi를 즐기기 위해 집에 C 공유기를 설치하고 싶다. 가능한 한 많은 곳에서 WiFi를 사용하고 싶기 때문에 집에 하나의 라우터만 설치하고 다음 두 라우터 사이의 거리를 최대한 넓게 설정하려고 합니다.

N개의 집에 C 라우터를 올바르게 설치하고 가장 가까운 두 라우터 사이의 거리를 최대화하는 프로그램을 작성하십시오.

기입

첫 번째 라인은 하우스 수 N(2 ≤ N ≤ 200,000)과 라우터 수 C(2 ≤ C ≤ N) 사이에 하나 이상의 공간을 지정합니다. 2번째 줄부터 N번째 줄까지는 집의 좌표를 나타내는 xi(0 ≤ xi ≤ 1,000,000,000)가 한 줄에 한 번씩 주어진다.

전체 코드

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

public class Main {
	static int C, N;
	static long() wifi;
	public static void main(String() args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		
		wifi = new long(N);
		for(int i=0; i<N; i++)
			wifi(i) = Long.parseLong(bf.readLine());
		Arrays.sort(wifi);
		find(wifi(N-1) - wifi(0));
	}
	static void find(long x) {
		long start = 0; long end = x;
		while(start <= end) {// 두 값이 같아지는 경우 끝나게 됨
			long mid = (start + end) / 2; // 공유기 사이의 가능한 거리
			if(find_dist(mid)) start = mid+1;
			else end = mid - 1;
		}
		System.out.println(start-1);
	}
	static boolean find_dist(long m) {
		int start = 0; int cnt = 1;
		for(int i=0; i<N; i++) {
			if(wifi(i) - wifi(start) >= m) {start = i; cnt++;}
		}
		if(cnt < C) return false;
		else return true;
	}
}

이진 검색의 중요한 부분은 while의 조건과 시작 및 종료의 업데이트 및 업데이트 조건입니다.
이 문제에서 정답이 될 길이는 라우터의 수를 C로 만드는 거리입니다.
따라서 조건은 숫자가 C(보다 작음) 또는 (보다 크거나 같음) 두 가지 경우로 나누어야 합니다.
while의 조건은 min ≤ max로 설정되어 있으므로 min = max+1의 형식을 취하게 됩니다.
정답인 Mid는 else 조건에 의해 mid-1이 되므로 결과 값은 결국 max 또는 min-1이 출력되어야 합니다.
while(min < max)의 경우 두 값이 같으면 while이 종료되는데 이 경우 무한 루프가 발생할 수 있다.