[백준] 공유기 설치 - Gold 4

[jusung-c]

문제 링크

https://www.acmicpc.net/problem/2110

문제 조건

집 N개가 수직선 위에 있을 때 공유기 C개를 설치할 것이다.
이 때 가장 인접한 두 공유기 사이의 거리를 최대로 설치해야 한다. 최대 사잇값을 구하라

• 같은 좌표를 가진 집은 없다.
• 집의 개수 N (2 ≤ N ≤ 20만)
• 공유기의 개수 C (2 ≤ C ≤ N)
• 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 10억)

---

아이디어

정답의 최대치를 생각해보자 집의 개수가 2개이고 0, 10억 좌표에 있을 때 공유기 2개를 설치하면 그 사이 거리가 10억이 되므로 int 범위로 해결 가능하다.

먼저 가장 단순하게 공유기 설치 거리를 1부터 최대치인 10억까지 검증해보면 된다.
검증할 때에는 정렬된 집 좌표 리스트를 돌면서 지정한 설치 거리로 공유기 C개를 설치할 수 있는지 판단하면 된다.
하지만 이때의 시간 복잡도는 O(10억 * 20만)이므로 시간 안에 풀 수 없다.

따라서 넓은 범위에서 최적의 조건을 찾아야 하므로 이분탐색을 떠올려야 하고, 그 중에서도 "최대 거리" 키워드를 통해 매개변수 탐색을 떠올려야 한다.

원래의 문제

• N개의 집에 C개의 공유기를 설치하려고 할 때 공유기 사이의 최대 거리는?
• 조건: N개의 집에 C개의 공유기를 설치해야 한다.
• 타겟: 공유기 사이의 최대 거리

조건과 타겟을 뒤집어서 만든 yes or no 결정 문제

• 공유기 사이의 거리가 h일 때 N개의 집에 C개의 공유기를 설치할 수 있는가?

뒤집은 결정 문제가 더 쉬운가? 꼭 확인
정렬된 집 리스트를 첫번째 집부터 지정한 h 거리로 되는대로 설치해봤을 때 C개가 가능한지만 판단하면 되므로 더 쉽다.

• 욕심쟁이 기법
  • 정렬 후 왼쪽부터 그냥 되는대로 h거리가 확보되는 순간 전부 설치해준다.
  • 어짜피 정렬이 된 상태라서 오른쪽 집으로 갈 수록 공유기간 거리가 짧아지기 때문이다.

결정문제는 Yessssss Noooooo 형태로 마지막 Yes를 찾으면 된다.

---

시간 복잡도

• 집 리스트 정렬하는데 O(N logN)
• yesOrNo 문제 푸든데 O(N)
• 이분탐색하는데 O(logN)

총 O(N logN)이고 N의 최댓값은 20만으로 시간 안에 풀이가 가능하다.

---

구현

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

public class Main {
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader br;
    static StringTokenizer st;
    static int N, C;
    static int max = Integer.MIN_VALUE;
    static int[] houses;

    public static void init() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        houses = new int[N];
        for (int i = 0; i < N; i++) {
            houses[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, houses[i]);
        }

        Arrays.sort(houses);
    }

    private static boolean yesOrNo(int h) {
        int cnt = 1;
        int pre = houses[0];

        for (int i = 1; i < N; i++) {
            if (pre + h > houses[i]) continue;

            cnt++;
            pre = houses[i];
        }

        return cnt >= C;
    }

    private static void pro() throws IOException {
        int start = 0;
        int end = max;
        int result = -1;

        while (start <= end) {
            int mid = (start + end) / 2;

            if (yesOrNo(mid)) {
                result = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        bw.write(result + " ");
    }

    public static void main(String[] args) throws Exception {
        init();

        pro();

        bw.close();
    }
}