백준 공유기 설치

공유기 설치

N개의 집 중 C개의 공유기를 설치하여, 인접한 공유기 사이의 거리를 최대로 만드는 문제이다.
문제를 처음 읽었을 때 “왜 이 문제가 이진 탐색 문제일까” 의문이 들 정도로 풀이 방향을 잘못 잡았다.
길이가 N인 일자 종이를 C-1등분해서 각 공유기가 설치된 집끼리 거리를 비교해 최소 거리를 찾는 방법을 생각했지만,
해당 방법은 비효율적일 뿐 아니라 허점이 많았다.
특히 N - 1 이 C - 1 의 약수가 아닐 경우 경우의 수가 너무 많아 일일이 파악할 수 없었다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        Arrays.sort(arr);
        long start = 1;
        long end = arr[n - 1] - arr[0] + 1;

        while (start < end) {
            long mid = (start + end) / 2;  // 최소 거리로 가정하고 탐색
            int count = 1;                 // 설치한 공유기 개수
            int lastIdx = 0;               // 마지막으로 공유기를 설치한 집의 인덱스

            for (int i = 1; i < n; i++) {
                long dist = arr[i] - arr[lastIdx];
                if (dist >= mid) {
                    lastIdx = i;
                    count++;
                }
            }

            if (count < c) {
                // 설치 가능한 공유기 개수가 C보다 적으면 최소 거리를 줄여야 함
                end = mid;
            } else {
                // 설치 개수가 C 이상이면 최소 거리를 늘려봄
                start = mid + 1;
            }
        }

        System.out.println(start - 1);
    }
}

해당 문제 역시 상한·하한 이진 탐색 개념뿐만 아니라, 설치 조건을 구현하는 부분이 까다로웠다.

핵심 아이디어

임의의 최소거리로 공유기를 설치한 수를 구해 C와 비교해 상한을 찾아 -1을해 반환하면 되는 문제였다.

그리고 공유기를 설치 할 수 있는 조건
공유기가 설치된 집과 집의 거리가 임의 최소거리보다 더 크거나 같으면 공유기를 설치 할 수 있다는 것을 파악하는데 도 어려웠다.