[백준] 2110번 - 공유기 설치

 

2110번: 공유기 설치

 

 

이전에 해결한 백준 1654번 랜선 자르기와 유사한 Parametric Search 문제이다. 알고 싶은 것은 가장 인접한 두 공유기 사이의 '최대 거리' 이다. 인접한 두 공유기 사이의 최대 거리 X가 될 수 있는 범위는 다음과 같다.

 

1 <= X <= 집 좌표 중 가장 큰 값

 

X가 될 수 있는 후보값 mid (= (left + right) / 2)에 대하여 인접한 두 공유기 사이의 최대거리가 mid일때 설치할 수 있는 공유기의 수를 반환하는 함수를 checkTrue(mid)라고 할 때, checkTrue가 공유기의 갯수 C보다 처음으로 작아질 때의 (길이 - 1) 이 구하고자 하는 X가 된다.

 

인접한 두 공유기 사이의 최대 길이가 d일 때 설치할 수 있는 공유기 수를 어떻게 구할 수 있을까?

 

house가 주어진 집의 좌표들을 오름차순으로 정렬한 배열이고 house[prev]가 이전 집의 좌표, house[next]가 다음 집의 좌표라고 하자.

house[prev] +  d > house[next] 라면 house[next]위치에는 공유기를 설치 할 수 없는데, house[next]에 공유기를 설치하게 되면 인접한 두 공유기 사이의 거리가 d보다 작아지기 때문이다. 따라서 house[prev] + d <= house[next]인 경우에만 공유기의 갯수를 +1 해주고 prev를 현재의 next로 수정 후 다음 인덱스를 확인한다.

static int checkTrue (int d) {
        
    int count = 1;

    int prev = 0;

    for (int next=1; next<N; next++) {
        if (house[prev] + d <= house[next]) {
            count++;
            prev = next;
        }
        else continue;
    }

    return count;
}

 

 

 

이렇게 구한 checkTrue의 반환값과 설치하는 공유기의 갯수 C를 비교 하여 설치해야 하는 공유기의 갯수보다 많거나 같으면 이분 탐색 다음 cycle의 탐색범위 최소값을 mid +1 로 수정하고 그렇지 않다면 right = mid 로 수정한다. 반복문은 checkTrue가 설치하는 공유기 수보다 '처음으로 작아질 때' 종료된다. 결과적으로 반복문이 종료된 시점의 left에 1만큼을 빼준 수를 반환해주면 된다.

static int upperBound (int key) {
        
    int left = 0;
    int right = max;

    while (left < right) {

        int mid = (left + right) / 2;

        if (checkTrue(mid) >= key) left = mid + 1;
        else right = mid;
    }

    return left - 1;
}

 

 

 

 

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static int N, max, house[];
    
    public static void main (String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        
        house = new int[N];
        
        for (int i=0; i<N; i++) {
            house[i] = Integer.parseInt(br.readLine());
            max = Math.max(max, house[i]);
        }
        
        
        Arrays.sort(house);
        max++;
        
        System.out.println(upperBound(C));
        
        br.close();
    }
    
    static int upperBound (int key) {
        
        int left = 1;
        int right = max;
        
        while (left < right) {
            
            int mid = (left + right) / 2;
            
            if (checkTrue(mid) >= key) left = mid + 1;
            else right = mid;
        }
        
        return left - 1;
    }
    
    static int checkTrue (int d) {
        
        int count = 1;
        
        int prev = 0;
        
        for (int next=1; next<N; next++) {
            if (house[prev] + d <= house[next]) {
                count++;
                prev = next;
            }
            else continue;
        }
        
        return count;
    }
}