[알고리즘 / 백준] 2110 - 공유기 설치

 

문제는 위와 같습니다. 저는 문제를 이해하는데 시간이 오래 걸렸는데... 주어진 공유기를 모두 설치하기 위해 떨어져 있어야 하는 집 사이의 최소 거리 중 최대 값을 구하는 것으로 생각하면 좋을 것 같습니다.

 

위 예제를 바탕으로 살펴보면,

공유기 설치 거리가 최소 2인 경우 1, 4, 8 또는 1, 4, 9 에 설치할 수 있습니다.

마찬가지로 공유기 설치 거리가 최소 3인 경우 1, 4, 8 또는 1, 4, 9 에 설치할 수 있습니다.

하지만, 공유기 설치 거리가 최소 4인 경우는 1, 8 또는 1, 9 아니면 4, 8 또는 4, 9 이렇게 최대 2개까지만 설치할 수 있습니다.

따라서 주어진 공유기를 모두 설치하기 위해서는 공유기 설치 최소 거리가 최대 3이므로 이 값이 출력됩니다.

 

또한, 최대한 많은 거리를 떨어져 있어야 하기 때문에 공유기는 항상 첫 집부터 설치하게 된다는 점을 알아두면 좋을 것 같습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin

n, c = map(int, stdin.readline().split())
houses = []
for _ in range(n):
    houses.append(int(stdin.readline()))

houses.sort()

minimum = houses[1] - houses[0]
maximum = houses[-1] - houses[0]
result = 0

while minimum <= maximum:
    mid = (minimum + maximum) // 2  # mid 는 Gap
    value = houses[0]
    count = 1
    for i in range(1, len(houses)):
        if houses[i] >= value + mid:
            value = houses[i]
            count += 1
    if count >= c:  # c 개 이상의 공유기를 설치할 수 있는 경우 거리를 더 넓히기
        result = mid
        minimum = mid + 1
    else:  # c 개 이상의 공유기를 설치할 수 없는 경우 거리를 더 좁히기
        maximum = mid - 1

print(result)

 

자바 코드는 다음과 같습니다.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] nc = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] houses = new int[nc[0]];
        for (int i = 0; i < houses.length; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(houses);

        int min = houses[1] - houses[0];
        int max = houses[houses.length - 1] - houses[0];
        int result = 0;

        while (min <= max) {
            int mid = (min + max) / 2;
            int value = houses[0];
            int count = 1;
            for (int i = 1; i < houses.length; i++) {
                if (houses[i] >= value + mid) {
                    value = houses[i];
                    count += 1;
                }
            }

            if (count >= nc[1]) {
                result = mid;
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }

        System.out.println(result);
    }
}

 

이진 탐색 문제의 경우 반복문 또는 재귀 함수를 사용할 수 있는데 이 문제는 반복문을 적용하는 것이 더 효율적이었습니다.