[백준/BOJ/JAVA] 2110 공유기 설치

 

 

도현이의 집 N개에 공유기 C개를 설치할 때, 가장 인접한 두 공유기의 최대 거리를 구하는 문제.

(단, 한 집에 하나의 공유기만을 설치할 수 있음)

 

 

min은 공유기를 설치할 수 있는 가장 짧은 거리인 1,

max는 공유기를 설치할 수 있는 가장 긴 거리인 (마지막 집 좌표 - 첫 집 좌표) 이다.

middle은 당연히 그 중간값이 된다.

 

일단 첫 집에 공유기를 하나 설치하고, 그 다음 집들과의 거리를 구해서 middle과 비교한다.

middle보다 크거나 같을 경우 해당 집에 공유기를 설치하고 그 집이 새로운 기준이 된다.

이걸 반복하며 공유기를 되는대로 설치한 뒤

설치된 공유기 개수와 설치할 공유기 개수 C를 비교하여 min, max 값을 조정한다.

 

코드를 보는게 이해가 더 빠를듯~?

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class BOJ_2110 {
    static int N, C;
    static int[] home;
    static long min, max; // 공유기 최소, 최대 거리
    static long res;
 
    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());
        C = Integer.parseInt(st.nextToken());
        home = new int[N];
 
        for(int i=0; i<N; ++i){
            st = new StringTokenizer(br.readLine());
            home[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(home);
 
        min = 1;
        max = home[N-1] - home[0];
 
        binarySearch();
 
        System.out.println(res);
    }
 
    private static void binarySearch() {
        while (min <= max){
            long middle = (max+min)/2;
            int prev = home[0]; // 무조건 처음 집에 설치
            long cnt = 1;        // 설치된 공유기 count
 
            for(int i=0; i<N; ++i){
                int distance = home[i] - prev;
 
                if(distance >= middle){ // 이전 공유기와의 거리가 middle 보다 크거나 같음
                    ++cnt;
                    prev = home[i];
                }
            }
 
            // 설치된 공유기 개수가 C보다 많으면 간격을 넓힘
            if(cnt >= C){
                min = middle + 1;
                res = Math.max(res, middle);
            } else{
                max = middle - 1;
            }
        }
    }
}
 

 

어려웠다.. 다른 사람 코드를 참고해서 풀었다.

풀고 나니 왜 어려웠지? 싶은 2194349808번째 문제..ㅎ