[2110] 공유기 설치

🔗 문제 링크

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

🔍 문제 설명

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

⚠️ 제한사항

• $(2 ≤ N ≤ 200,000), (2 ≤ C ≤ N)$

• $x_i (0 ≤ x_i ≤ 1,000,000,000)$

---

🗝 풀이 (언어 : Java)

문제를 거꾸로 생각하면 좀 더 쉽게 풀 수 있는 문제이다. 좌표별로 공유기를 이리저리 놔보는 것보다, 공유기간 간격의 거리별로 가능한 것들의 최대값을 구하는 것이 구현하기 쉽다. 집들을 좌표순으로 정렬하고, 맨 처음 집에 1개를 설치하고 그 이후에 임의의 거리(distance)만큼의 간격씩 공유기를 C개 이상 설치할 수 있는지 판단하여 가능하다면 정답 후보의 거리값이다. 이 과정을 거리별로 다 수행하면 시간 복잡도가 오래걸리므로, 거리들을 조회하는 것이 정렬된 순이라는 점을 이용해서 이분 탐색으로 시간복잡도를 줄인다. 시간 복잡도를 계산해보면 주어진 집들을 정렬하면 $O(NlogN)$이고 이분 탐색으로 타겟 거리를 고르는 작업은 $O(logX)$인데 이때마다 N개의 집을 반복문으로 거치므로 $O(NlogX)$가 되어서, 총 시간복잡도는 $O(NlogN + NlogX)$이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    // 해당 거리만큼 떨어진 공유기 C개 이상 설치 가능한지 판별
    private boolean isPossible(int n, int c, int[] houses, int distance) {
        // 설치한 공유기 수, 직전 공유기 위치, 최초 시작점에 하나 설치 고정(최대한 많이 설치하려면 되는대로 설치)
        int count = 1, before = houses[0];
        for (int i = 1; i < n; i++) {
            if (houses[i] - before >= distance) {
                count++;
                before = houses[i];
            }
        }
        return count >= c;
    }

    private int findRouterDistance(int n, int c, int[] houses) {
        // 집들을 좌표순으로 정렬
        Arrays.sort(houses);
        // 문제를 거꾸로 생각해서 공유기를 c개 놓는게 가능한 거리중 최대값을 구함
        int left = 0, right = 1000000000, max = 0;
        while (left <= right) {
            int distance = (left + right) / 2;
            // 해당 거리간격으로 공유기를 c개 이상 설치가능 OR 불가능
            if (isPossible(n, c, houses, distance)) {
                left = distance+1;
                max = distance;
            } else {
                right = distance-1;
            }
        }
        return max;
    }

    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()), c = Integer.parseInt(st.nextToken());
        int[] houses = new int[n];
        for (int i = 0; i < n; i++)
            houses[i] = Integer.parseInt(br.readLine());
        br.close();
        Main main = new Main();
        System.out.println(main.findRouterDistance(n, c, houses));
    }
}