[BOJ] 2110. 공유기 설치

이분탐색을 이용한 문제였다.

집 좌표의 범위가 10억 그리고 최대 값을 구하는 문제여서 이분탐색으로 접근할 수 있었다. 우선 첫번째 집에 공유기를 설치한 것을 가정한 후 이분탐색을 이용해 설치길이를 정하여 다음집에 설치할 수 있는지 없는지 여부를 확인하며 답을 찾아갔다. 

package algosutdy1;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main_bj_2110_공유기설치 {
    static int N, C;
    static long[] house;
    static long answer;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        house = new long[N];
 
        for (int i = 0; i < N; i++) {
            house[i] = Long.parseLong(br.readLine());
        }
 
        Arrays.sort(house);
 
        answer = 0;
        binarySearch();
 
        System.out.println(answer);
    }
 
    static void binarySearch() {
        long left = 1;
        long right = house[N - 1] - house[0];
 
        while (left <= right) {
            long mid = (left + right) / 2;        //체크해야할길이
 
            int check = 1;
            long cur = house[0];
 
            for (int i = 1; i < N; i++) {
                long next = house[i];
 
                if (next - cur >= mid) {
                    cur = next;
                    check += 1;
                }
            }
 
            if (check >= C) {
                answer = Math.max(answer, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
}