[BOJ] 백준 2110 - 공유기 설치 풀이

1. 문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

2. 풀이

이분탐색을 활용한 골드V 문제이다. 문제를 풀면서 이분탐색의 Upper_bound, Lower_bound가 정확히 기억이 나지 않아 글을 찾아보면서 문제를 해결했다.

https://blog.naver.com/bestmaker0290/220820005454

알고리즘 기초 - Lower Bound & Upper Bound

https://www.acmicpc.net/blog/view/109

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

먼저 문제를 파악해보자!

집의 개수와 설치해야하는 공유기의 수, 그리고 집들의 좌표가 주어진다. 이 문제의 핵심은 인접한 공유기의 거리 중에서 최소값 중 최대값이다. 힌트에서도 나와 있듯이 1, 4, 8로 설치했을 때 인접한 공유기의 최소값은 3이 된다. 만약 1에 설치한 후 8, 9에 설치했다면 인접한 공유기의 거리중 최소 값은 1이 된다. 

그렇다면 이분탐색을 어떻게 적용해야 할까?

문제에서 주어지는 것은 좌표이고 답으로 요구하는 것은 '거리'이다. 이 거리에 따라 설치할 수 있는 공유기의 개수가 달라진다. 

결국 거리를 탐색의 범위로 설정하고 이분탐색을 진행하면서, 해당 거리에 대해 설치 가능한 공유기의 개수에 따라 탐색하는 거리의 범위를 좁혀나가는 방식으로 적용하면 된다.

 

3. 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Main {
    static int[] line;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 집의 개수
        int C = Integer.parseInt(st.nextToken()); // 공유기의 개수

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

        int mid = 0;
        int start = 1;
        int end = line[N - 1] - line[0] + 1;

        while (start < end) {
            mid = (start + end) / 2;

            if (install(mid) < C) {
                end = mid;
            }
            else {
                start = mid + 1;
            }

        }

        bw.write(Integer.toString(start - 1));
        bw.flush();
        bw.close();
        br.close();
    }

    private static int install(int dist) {

        int cnt = 1; // 첫 번째 집에는 무조건 설치
        int endLocated = line[0];

        for (int i = 1; i < line.length; i++) {
            int lo = line[i];

            if (lo - endLocated >= dist) {
                cnt += 1;
                endLocated = lo;
            }
        }
        return cnt;
    }
}