공유기 설치 - 2110번

풀이 방법

L이 증가 할수록 공유기의 개수를 감소한다.
만약 크기가 L이고 i번째에 공유기를 설치했다면 다음 공유기를 설치할 좌표(j)는 아래 공식과 같다.
$$ X[i] + L <= X[j] $$
만약 L보다 큰 어떤 수 L1이라면 다음 공유기를 설치 할 좌표(k)는 j <= k라는 것을 알 수 있다.
$$ X[i] + L1 <= X[k]\ 이므로, \ j <= k $$
따라서 L이 증가할수록 공유기의 개수는 단조감소함수이기 때문에 이분법으로 풀이가 가능하다.

전체 코드

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt(); int M = in.nextInt();
        ArrayList<Integer> h = new ArrayList<Integer>();
        for(int i = 0; i < N; ++i) {
            int v = in.nextInt();
            h.add(v);
        }
        h.sort(Comparator.naturalOrder());
        int l = 1; int r = h.get(N-1) - h.get(0);
        int mid = 0;
        while(l <= r) {
            mid = (l + r) / 2;
            int t = 0, cnt = 1;
            for(int i = 1; i < N; ++i) {
                if((h.get(i) - h.get(t)) >= mid) {
                    t = i;
                    cnt++;
                }
            }
            if(cnt >= M)
                l = mid + 1;
            else
                r = mid - 1;
        }
        System.out.printf("%d", r);
    }
}

[링크] https://www.acmicpc.net/problem/2110