[백준] 2110: 공유기 설치 - JAVA
https://www.acmicpc.net/problem/2110
풀이
공유기를 C개 설치하면서 가장 인접한 두 공유기 사이의 거리를 최대ㅐ로 하는 문제이다.
공유기 사이의 거리를 기준으로 이분탐색을하여 풀었다.
이분탐색을 해야하므로 입력을 받아 배열을 정렬했다.
left와 right를 놓고 mid를 공유기 사이의 거리로 하여 그 거리만큼 띄웠을 때 몇개의 공유기를 설치할 수 있는지 판단했다.
설치가능한 공유기의 개수가 c보다 작다면 right를 mid로 줄이고
그렇지 않다면 left를 mid+1 로 증가시켰다.
메모리: 28912KB
시간: 312ms
언어: Java 11
코드
import java.util.*;
import java.io.*;
public class Main {
static int[] arr;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int left = 1;
int right = arr[n - 1] - arr[0] + 1;
while (left < right) {
int mid = (left + right) / 2;
int cnt = installWifi(mid);
if (cnt < c) {
right = mid;
} else {
left = mid + 1;
}
}
System.out.println(left - 1);
}
private static int installWifi(int n) {
int cnt = 1;
int pos = arr[0];
for (int i = 1; i < arr.length; i++) {
int dist = arr[i] - pos;
if (dist >= n) {
cnt++;
pos = arr[i];
}
}
return cnt;
}
}