코드
package com;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] h;
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int c = sc.nextInt();
h = new int[n];
for(int i=0; i<n; i++) {
h[i] = sc.nextInt();
}
//이분탐색하기 위해 먼저 정렬
Arrays.sort(h);
int min = 1; //최소거리
int max = h[n-1] - h[0] + 1; // 최소거리의 최댓값
while(min < max) {
int mid = (max + min) / 2;
//가능한게 c보다 작으면 max 줄임
if(possible(mid) < c) {
max = mid;
//c이상이면 min 늘림
}else {
min = mid + 1;
}
}
System.out.println(min - 1);
}
//distance에 대해서 몇대를 설치할 수 있는지 return
private static int possible(int distance) {
int cnt = 1;
//제일 마지막에 공유기 설치한 곳
//여기랑 비교해서 설치할 수 있는지 파악
int last = h[0];
for (int i = 1; i < h.length; i++) {
int now = h[i];
if(now - last >= distance) {
cnt++;
last = now;
}
}
return cnt;
}
}풀이
1.
가장 인접한 두 공유기 사이의 거리를 최대한으로 하길 원하므로 이 값을 가지고 놀아야한다.
공유기 개수 C가 주어지므로
두 공유기 사이의 거리를 늘렸다 줄였다 하면서 각 거리때마다 C개를 세울 수 있는지 판단한다.
2.
각 거리때마다 공유기 몇개를 세울 수 있는지 판별하기
집의 좌표를 오름차순으로 정렬하고 나서 첫번쨰 집부터 하나씩 세워본다.
첫번째 집에는 무조건 세운다고 하고, 그 다음 좌표들을 돌아보면서 이전에 설치한 집과 거리를 비교해서 가능하면 세우는 식
여기서 그리디적인 개념이 들어가는데, 거리비교를 할 때는 무조건 이전에 설치한 집이랑만 비교하면 된다.
이전에 설치한 집이 아니라 이전 집과 비교를 하게 되면
예를 들어
모든 집사이의 거리가 1인데, 공유기 사이 거리가 3이면 끝까지 공유기를 세울 수 없다.
정렬하고 그냥 이전에 설치한 집이랑만 계속 비교하면 된다.
3.
각 거리가 가질 수 있는 범위를 지정 min ~ max
여기서 이분탐색
min, max의 평균으로 거리를 지정한 다음 2에서 하는 판별을 하면 된다.
- 판별한 결과가 C 보다 작으면 거리가 커서 안되는 거니까 max를 줄인다.
- 판별한 결과가 C 보다 크면 거리가 작아서 거리를 늘릴 수 있다는 뜻이므로 min을 늘린다.
ㅋ