백준 2110번 공유기 설치 java8

9234 단어 코테코테
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;


public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int house = sc.nextInt();
        int totalWifi = sc.nextInt();
        int[] cordi = new int[house];

        for(int i=0; i<house ; i++) {
            cordi[i] = sc.nextInt();
        }
        Arrays.sort(cordi);

        int lo = 1;
        int hi = cordi[house-1]-cordi[0];
        int answer = (lo+hi)/2;

        while ((hi >= lo)) {
            int mid = (lo+hi)/2;
            //answer = (lo+hi)/2; // 이 한줄이 바이너리서치


            int count = 1;
            int curStart = cordi[0];

            //answer 간격으로 설치하면 몇대 깔리니 측정
            for(int i=0 ; i< house ; i++) {
                int dist = cordi[i] - curStart;
                if(dist >= mid) {
                    count++;
                    curStart = cordi[i];
                }
            }

            if(count >= totalWifi) {
                answer = mid;
                // 공유기 수가 너무 많아!
                // 좀더 넓은 간격으로 설치해
                //answer = (lo+hi)/2;
                lo = mid+1;
            }
            else {
                // 좁은간격으로 설치할꺼니까
                hi = mid-1;
            }

        }
        System.out.println(answer);
        return;
    }

}
/*
//
5 3
1
2
8
4
9

//
7 2
1
2
3
4
5
6
7


 */

좋은 웹페이지 즐겨찾기