(코테) 백준_2110_공유기 설치 *이분탐색

 

 

 

 

 

 

 

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

public class Main {
    static int N, C;
    static int[] houses;

    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);  // 좌표 오름차순 정렬

        // 이분 탐색 시작: 최소 거리 (left), 최대 거리 (right)
        int left = 1;  // 가능한 최소 거리
        int right = houses[N - 1] - houses[0];  // 가능한 최대 거리
        int answer = 0;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (canInstall(mid)) {
                answer = mid;       // 거리 가능한 경우, 더 큰 거리 시도
                left = mid + 1;
            } else {
                right = mid - 1;    // 거리 너무 큼 → 줄이자
            }
        }

        System.out.println(answer);
    }

    // 최소 거리 distance로 공유기 C개 설치 가능한지 확인
    static boolean canInstall(int distance) {
        int count = 1;  // 첫 번째 집에 설치
        int lastInstalled = houses[0];

        for (int i = 1; i < N; i++) {
            if (houses[i] - lastInstalled >= distance) {
                count++;
                lastInstalled = houses[i];
            }
        }

        return count >= C;  // 설치한 개수가 C개 이상이면 true
    }
}