공유기 설치 2110

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

중간값 집간에거리
c와 비교할 값은 집간거리를 통해 몇개 와이파이 설치가능한지 구하는 함수

대략 어떻게 풀어야할지 감을 잡고 이대로 구현하면되는지 다른 사람의 풀이를 참고하였다

시간복잡도
nlog(xi)

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

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int c = Integer.parseInt(input[1]);

        int[] arr = new int[n];
        for(int i = 0; i < n; ++i)
        {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int left = 0;
        int right = 1000000000;
        int cand = 0;
        int ans = 0;
        while(left <= right)
        {
            cand = (left+right)/2;
            if(cal(arr, cand) >= c)
            {
                ans = Math.max(ans, cand);
                left = cand+1;
            }
            else
            {
                right = cand-1;
            }

        }

        System.out.println(ans);

    }
    public static int cal(int[] arr, int cand)
    {
        int ret = 1;

        int start = 0;
        for(int i = 0; i+1 < arr.length; ++i)
        {
            if((arr[i+1] - arr[start]) >= cand)
            {
                start = i+1;
                ret++;
            }
        }

        return ret;
    }
}