[백준 2110] 공유기 설치

 

이분 탐색으로 구현했다.

1. 임의 변수 mid 를 최대 거리로 사용했다.

2. 최대한 많은 곳에서 사용하려면 그리디한 방법으로 구현해야 한다.

2-1. 따라서 제일 좌측 집에는 반드시 설치한다.

3. mid 거리마다 거리가 일치하거나 가장 좌측 가까이 있는 집에 설치한다.

4. 카운트를 비교하여 left, right 를 조정한다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int c = sc.nextInt();
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        Arrays.sort(a);
        int left = a[0];
        int right = a[n-1] - a[0];
        while(left <= right) {
            int mid = (left + right)/2;
            int prev = a[0];
            int cnt = 1;
            for(int i=1; i<n; i++) {
                int distance = a[i] - prev;
                if(mid <= distance) {
                    cnt++;
                    prev = a[i];
                }
            }
            if(cnt >= c) left = mid + 1;
            else right = mid - 1;
        }
        System.out.println(left - 1);
    }
}