백준 2110번 공유기 설치 java8
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
*/
Author And Source
이 문제에 관하여(백준 2110번 공유기 설치 java8), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@d-h-k/백준-2110번-공유기-설치-java8저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)