[백준] 2110번:공유기 설치 (Java 자바)
문제
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
풀이 및 소스코드
ㅋㅋㅋ문제 이해가 안됐던 문제다..
설명해보면
현재 집의 좌표가 arr = (1, 2, 4, 8, 9) 라고 하자 ! (백준 예제임)
start = 1
end = arr[n-1]-arr[0] // 공유기를 놓을 수 있는 최대 거리
으로 초기화를 할 수 있다.
즉, 1에 놓고 9에 놓으면 최대거리 8 !! 이렇게 양 끝을 잡고 이분탐색을 통해 c(3)개의 공유기가 놓이면서, 공유기 사이의 최대거리를 구하면 된다.
이어서 설명하자면 mid는 (9-1)/2 인 4가 된다.
1. 최대 거리 : 4
첫번째 집에 공유기를 설치한다.
현재 공유기 위치 : home[0]
다음 공유기를 설치 할 수 있는 최소 거리 : now = home[0]+mid
집들의 좌표를 처음부터 비교해서 다음 공유기를 설치할 수 있는지 확인한다.
arr = (1, 2, 4, 8, 9) now보다 작음. 설치불가 !
arr = (1, 2, 4, 8, 9) now보다 작음. 설치불가 !
arr = (1, 2, 4, 8, 9) now보다 큼. 설치 가능.
=> now = home[3]+mid
arr = (1, 2, 4, 8, 9) now보다 작음. 설치 불가 !
cnt 는 총 2개로, c보다 작으므로 간격을 줄여서 공유기를 설치해야한다.
간격을 줄여야하므로, end = mid-1 로 바꾼다.
2. 최대 거리 : 3
arr = (1, 2, 4, 8, 9) now보다 작음. 설치불가 !
arr = (1, 2, 4, 8, 9) now보다 큼. 설치 가능.
=> now = home[2]+mid
arr = (1, 2, 4, 8, 9) now보다 큼. 설치 가능.
=> now = home[3]+mid
arr = (1, 2, 4, 8, 9) now보다 작음. 설치 불가 !
3개 설치가 되는 거리 3을 찾아냈다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int[] home = new int[n];
for(int i=0;i<n;i++) {
home[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(home); //오름차순 정렬
int start = 1; //시작점
int end = home[n-1]-home[0]; //공유기의 최대거리
int res = 0;
while(start<=end) {
int cnt = 1;
int mid = (start+end)/2;
int now = home[0]+mid; //첫번째 공유기 설치+거리
for(int i=0;i<n;i++) {
if(now<=home[i]) { //만약에 인접한 공유기와 mid 이상의 차이가 나면
now = home[i]+mid;
cnt ++; //공유기 설치 !
}
}
boolean flg = cnt>=c? true: false;
if(flg) {//c이상 설치가 가능할 때 mid값 들 중 최댓값을 구하자!
res = Math.max(res, mid);
//최댓값을 찾는 것이므로
start = mid+1;
}else {//공유기 너무 적게 설치 ㅠ 간격을 줄이자.
end = mid-1;
}
}
System.out.println(res);
}
}