[백준] 2110. 공유기 설치

문제 링크

[백준] 2110. 공유기 설치

풀이 과정

집이 20만개까지 존재할 수 있으므로, 집들 사이의 거리를 하나씩 비교해보면서 공유기를 설치해보면 시간초과가 발생하게 됩니다.

따라서, 문제의 답을 미리 결정해두고, 정해둔 답이 모순이면 다시 답을 설정하는 방식의 이분 탐색으로 문제를 풀어야 합니다.

for (int i = 0; i < N; i++) loc[i] = sc.nextInt();

Arrays.sort(loc);

int low = 0;
int high = (int) 1e9;
int answer = 0;

배열에 집 좌표를 입력받은 후, 오름차순 기준으로 정렬합니다. 집의 좌표는 0이상 10억 이하이므로, 초기 범위는 집의 좌표로 가능한 양 끝 0과 10억으로 설정합니다.

while (low <= high) {
    int mid = (low + high) / 2;
    int end = loc[0];
    int cnt = 1;

    for (int i = 1; i < N; i++) {
        if (loc[i] - end >= mid) {
            cnt++;
            end = loc[i];
        }
    }

    if (cnt >= C) {
        answer = mid;
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

중간값 mid 는 가장 인접한 공유기 사이의 거리를 의미합니다. 우리는 mid 값으로 공유기를 설치해본 뒤, 공유기 개수가 C 이상이면, mid의 값을 더 올려 테스트해볼 수 있습니다.

각 집에서 바로 이전 집까지의 거리가 정해둔 공유기 설치 거리 mid 이상이면, 공유기 설치가 가능합니다.

예를 들어, 위 예시에서 공유기 사이의 최소 거리를 2로 설정했다면, 거리 2 이상 띄워져 있는 집들에 공유기를 설치가 가능합니다. 맨 처음, 좌표 1에 공유기를 설치한 뒤, 거리가 3만큼 떨어진 좌표 4에 공유기를 설치하고, 그로부터 거리가 4만큼 떨어진 좌표 8에 공유기를 설치할 수 있습니다.

위 예시에서는 최소 거리(mid)를 2로 설정했지만, 실제로 위 그림을 통해 우리는 최소 거리가 3(좌표 1-4-8에 설치)임을 확인할 수 있습니다. 하지만, 이를 코드로 확인하기 위해서는, mid 값의 lower bound를 올림으로써 범위도 좁히며, 동시에 더 높은 정답을 찾을 수 있게 됩니다.

코드

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();
        int[] loc = new int[N];

        for (int i = 0; i < N; i++) loc[i] = sc.nextInt();

        Arrays.sort(loc);

        int low = 0;
        int high = (int) 1e9;
        int answer = 0;

        while (low <= high) {
            int mid = (low + high) / 2;
            int end = loc[0];
            int cnt = 1;

            for (int i = 1; i < N; i++) {
                if (loc[i] - end >= mid) {
                    cnt++;
                    end = loc[i];
                }
            }

            if (cnt >= C) {
                answer = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        System.out.println(answer);
    }
}