백준 알고리즘 2110번: 공유기 설치

문제 정보

---

 

2110번: 공유기 설치

 

핵심

---

공유기 C개를 설치할 때, 가장 인접한 두 공유기 사이의 거리의 최대값을 구하는 것!

N개의 집에 공유기 C개를 설치하고자 한다. 내 풀이의 방식은 직전에 풀었던 문제들처럼 이분 탐색을 활용하여 문제를 풀이한다.

 

가장 인접한 공유기 사이의 거리의 최대값을 기준으로 두고, 이에 대한 이분 탐색으로 답을 구하는 과정이다

1. 될 수 있는 가장 인접한 공유기 사이의 거리의 최소값은 1이다.
2. 될 수 있는 가장 인접한 공유기 사이의 거리의 최대값은 (가장 큰 좌표를 가지는 집 - 가장 작은 좌표를 가지는 집) 이다.
3. 최대와 최소 사이 중간 지점을 기준으로, 공유기 사이 거리라고 생각하고 몇 개의 공유기가 설치되는 지 확인한다
4. 원하는 개수 (C) 보다 적게 설치된다면, 거리가 먼 것이므로 max 값을 수정한다 (max = mid)
5. 원하는 개수 (C) 보다 많이 설치된다면, 거리가 가까운 것이므로 min 값을 수정한다 (mid = mid + 1)
6. 원하는 개수에 맞게 설치되더라도, 같은 공유기 개수를 가지는 거리의 최대값을 구하는 것이므로 5번과 동일한 로직을 수행한다
7. 반복이 종료되었을 때의 min 값은 구하고자 하는 값(같은 공유기 개수를 가지는 거리의 최대값)의 다음 값이므로 min - 1 이 구하고자 하는 값이다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int[] houses = new int[N];

        for(int i=0; i<N; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(houses);

        int min = 1;
        int max = houses[N-1] - houses[0] + 1;

        int result = 0;
        while(min < max) {
            int mid = (min + max) / 2;
            // mid : 가장 인접한 공유기 사이의 거리 최소값

            int prev = houses[0];
            int count = 1;
            for(int i=1; i<N; i++) {
                int current = houses[i];
                if(current-prev >= mid) {
                    count++;
                    prev = current;
                }
            }

            if(count < C) {
                max = mid;
            } else {
                min = mid + 1;
            }
        }
        System.out.println(min-1);
    }
}

 

Source Code on GitHub

---