1. 문제 설명 📌

2. 접근 방식 🗃️

KEY WORD : Binary Search, Parametric Search, Greedy Algorithm

(1) 집 간의 최소 거리와 최대거리를 활용해, 임의의 거리 d를 산정한다.
(2) '모든 공유기 사이의 거리가 최소한 d 이상인가?'를 boolean 값으로 계산한다.
(3) (2)번이 true면, start = mid + 1로 거리를 상향 조정, false면 end = mid - 1로 하향 조정한다.
(4) start와 end가 엇갈렸을 때, start - 1이 답이다.

(1) Parametric Search 이용

해당 문제는 가장 인접한 두 공유기 사이의 최대 거리 즉 최소값 중에서 최대값을 구하는 최적화 문제이다. 최적화 문제는 바로 풀기 어렵기 때문에, 여러개의 결정 문제로 변환한다. 여기서는

최적화 문제	결정 문제
나올 수 있는 최소 거리 사이에서 최대값 구하기	두 인접한 공유기 사이의 최소 거리를 `d` 로 두었을 때, 모든 공유기 사이에서 d 이상이 만족하는가?

로 바꾼다.

이러면 f(d) = true 중에서 가장 오른쪽에 있는 값을 구하면, 그때의 d가 우리가 바라는 두 공유기 사이에서 될 수 있는 최대 거리이다.

(2) f(d)를 구하는 법 `Greedy Algorithm`

최대 거리 산정을 위해서는 최대한 왼쪽에 있는 집부터 선택해 사용해야 한다. 그래야 다음 공유기를 설치할 장소의 거리를 최대한 크게 만들 수 있기 때문이다.

부분적인 최선의 해답이 곧 전체의 최선의 해가 되므로, Greedy Algorithm이 성립한다.

3. 코드 소개 🔎

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;


public class Main {
    static int N, C; // 각각 집의 개수,공유기 개수
    static int [] homes; // 집의 좌표들

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        homes = new int [N];
        for (int i = 0; i < N; i++) {
            homes[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(homes);
        System.out.println(binary_search());
    }

    public static int binary_search(){
        int start = 0;
        int end = 1000000001;

        while (start <= end) {
            int mid = start + (end - start)/2;
            if(f(mid)) start = mid + 1;
            else end = mid - 1;
        }
        return start - 1;
    }

    public static boolean f(int d) {
        int router_cnt = C - 1;
        int prev_router_loc = homes[0];
        for (int i = 1; i < N; i++) {
            if(homes[i] - prev_router_loc < d) continue;
            prev_router_loc = homes[i];
            router_cnt--;

            if(router_cnt == 0) {
                return true;
            }
        }
        return false;
    }
}