문제
문제 링크 : https://www.acmicpc.net/problem/2110
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력 1
5 3
1
2
8
4
9
예제 출력 1
3
힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.
문제 접근 방법
-문제의 예시대로 각각의 집 들과 공유기의 갯수가 있다고 해보자
(그림은 차후에 넣기) 여기는 기본
-그렇다면 여기서
최대거리 : 9 - 1 = 8
최소거리 : 1 이 될껏이다.
(최소거리에서 너무 많은 경우 그림)
(최대 거리에서 너무 없는 경우)
거리를 찾을떄 이진탐색 parametric search 방식으로!!! 그리고 최대를 찾는것이므로 이거리보다 더 크지 않다면? 집을 포함하는 식으로 가야 된다.
(거리 미달 그림)
3가지 경우 :
-그래서 만약 공유기의 갯수가 더 많다면....?
더 줄이기 위해서 거리를 늘려야되므로 중간과 끝에 대해서만 탐색
-공유기 갯수와 거리탐색시 딱 공유기 갯수가 같은경우...?
최대를 찾는것이 목표이므로 거리를 더 늘려서 탐색!
-공유기의 갯수가 거리탐색시 공유기 갯수보다 더 적다면?
거리를 더 줄여서 공유기 갯수를 늘려야 된다.
풀이
package 이진탐색;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class 공유기설치 {
static int[] arr;
static int result;
public static void main(String[] args) throws IOException {
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 result = calculateMaxLength(1, arr[N - 1] - arr[0], N, C);
//mid는 무엇이냐? 거리라는거지 즉 왼쪽 오른쪽을 당겨서 최대 거리를 구하는거라도
System.out.println(result);
}
private static int calculateMaxLength(int start, int end, int N, int C) {
if (start > end) {
return result;
}
int mid = (start + end) /2;
int count = 1;
int last_house = arr[0]; // 업데이트 되어야 한다.
for (int i = 1; i < N; i++) {
if(arr[i] - last_house >= mid) {
count++; //count를 추가한다.
last_house = arr[i]; // last_house를 업데이트 해서 이전집과의 거리로 해야 된다.
}
}
if (count >= C) { //count가 같거나 혹은 더 많은 경우는 길이를 늘려서 수를 줄이거나 최대로
result = mid;
return calculateMaxLength(mid+1, end, N, C);
}
else { // count < C
return calculateMaxLength(start, mid - 1, N, C);
}
}
}
유의 해야 될점
-처음에는 양 끝에 공유기를 놓고 시작해야되는줄 알았으나 처음에만 두고 최소 최대 거리를 이진 탐색을 통해 찾아야 된다.
-그리고 거리가 미달인 경우에는 포함하지 않기 위해서 직전의 집과 거리를 비교해야된다!
++) 메서드로 따로 뺴지 않고 while문으로 풀어도 될듯함
