BOJ02110 공유기 설치

https://www.acmicpc.net/problem/2110 (opens new window)

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

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

파라메트릭 서치

int left = 1;
int right = homes[n - 1] - homes[0];

int result = 0;
while (left <= right) {
    int mid = (left + right) / 2;
    int start  = homes[0];
    int count = 1;

    for (int i = 0; i < n; i++) {
        if (homes[i] - start >= mid) {
            count++;
            start = homes[i];
        }
    }

    if (count >= c) {
        result = mid;
        left = mid + 1;
    } else {
        right = mid - 1;
    }
}

제출 코드

아래는 최종 제출 코드이다.

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

public class BOJ2110 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt(); // 집의 개수
        int c = scanner.nextInt(); // 공유기의 개수
        int[] homes = new int[n];

        for (int i = 0; i < n; i++) {
            homes[i] = scanner.nextInt();
        }

        Arrays.sort(homes);

        int left = 1;
        int right = homes[n - 1] - homes[0];

        int result = 0;
        while (left <= right) {
            int mid = (left + right) / 2;
            int start  = homes[0];
            int count = 1;

            for (int i = 0; i < n; i++) {
                if (homes[i] - start >= mid) {
                    count++;
                    start = homes[i];
                }
            }

            if (count >= c) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        System.out.println(result);
    }
}

#BOJ #이분 탐색 #매개 변수 탐색 #파라메트릭 서치