[백준] 2110 공유기 설치

www.acmicpc.net/problem/2110

2110번: 공유기 설치

2021-02-23

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main2110 {
    public static int N, C, arr[];
    public static boolean make(int gap) {
        int prev = arr[0];
        int count = 0; // count 공유기
        for(int i = 1; i < N; i++) {
            if(arr[i] - prev >= gap) { // 현재 값 - prev가 gap보다 크거나 같아야한다.
                count++;
                prev = arr[i]; // 다음 gap을 구한다
            }
        }
        return count >= C;
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new int[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(bf.readLine());
            arr[i] = Integer.parseInt(st.nextToken().trim());
        }
 
        Arrays.sort(arr); // 오름차순 정렬
 
        C--; // 무조건 첫 번째에 공유기를 설치한다고 가정한다.
        int start = 1;
        int end = arr[N-1] - arr[0];
        int answer = 0;
        while(start <= end) {
            int mid = (start + end) / 2;
 
            if(make(mid)) { // 공유기가 C보다 더 많이 설치되었다면
                answer = Math.max(answer, mid);
                start = mid + 1;
            } else end = mid - 1; // 만들 수 없다면 간격이 너무 크다라는 의미이므로, 간격을 좁힌다.
        }
        System.out.println(answer);
    }
}

 

#문제풀이

문제를 이해하는게 좀 힘들었었다.

 

아래 그림으로 간단하게 설명을 하자면, 문제에서 가장 인접한 두 공유기 사이의 거리를 최대를 구하라 라고 주어졌다.

그 의미는 단순히 공유기를 놓을 수 있는 경우의 수를 다 구해서 그 공유기들 중 두 개의 공유기를 뽑아 최대거리를 구하라는 것이 아니다. C개의 공유기를 모두 놓은 상태에서 두 공유기들의 사이가 일정한 값 이상이어야 한다는 것이다.

즉, 문제의 힌트(공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.) 에서도 확인할 수 있다. 공유기1과 공유기4 사이의 거리는 3이고, 공유기4에서 3이상의 거리에다가 놓을 수 있는 경우는 8또는 9이다. 

 

만약에 공유기1에 놓고, 그 다음 공유기를 8에 놓는다면 두 공유기 사이의 거리가 7이 되지만, 그 다음에 집15는 존재하지 않으므로 C개의 공유기를 다 놓을 수가 없다.

 

그래서 문제를 풀 때, 거리에 집중을 하여 풀었다. 즉, 이분탐색으로 풀 때 mid 값을 거리 사이의 gap으로 생각하였다.

 

자세한 내용은 주석으로 달았다.