[백준] 2110 공유기 설치(Gold.4) - 이진 탐색

문제

공유기 설치

문제 해설

처음엔 완전 탐색 아이디어를 떠올렸다. 아래 그림과 같이 모든 경우의 수를 구한 뒤 최대 거리를 출력하는 방식이다. 그런데 이 문제는 이분 탐색 문제다... 완전 탐색으로 풀면 시간 초과 뜰 확률이 100%다..

최대한 이분 탐색으로 어떻게 풀지 생각해봤는데 도저히 아이디어가 떠오르지 않아서 이 블로그를 참고해서 풀었다.

• 공유기의 개수는 최소 2개이고 공유기 사이 거리의 최대 값을 찾아야 한다. 공유기 사이 거리가 최대가 되기 위해서 첫 번째 집은 항상 공유기가 설치되어야 한다.
• low, high, mid값은 무엇으로 설정해야 할까? 전에 푼 이분 탐색 문제를 떠올려 보자. 대부분 내가 구하고자 하는 값의 최소, 최대, 목표 값으로 잡고 이분 탐색을 진행했다. 그럼 이 문제에서 mid 값은 공유기 사이 거리가 되어야 하고 low와 high는 최소 거리, 최대 거리로 설정한다.
• 이제 이분 탐색을 진행하자.
  1. 집을 순회하며 현재 집과 다음 집의 거리와 mid값을 비교한다.
     • 현재 집과 다음 집의 거리 >= mid라면 공유기 설치가 가능하므로 카운팅
  2. cnt >= 공유기 개수: 거리를 더 늘려야 하기 때문에 오른쪽을 탐색한다.(`low = mid + 1)
     • 공유기 사이 거리의 최댓값을 구해야 하기 때문에 cnt == 공유기 개수일 때 공유기 사이 거리(mid)를 늘리기 위해 오른쪽을 탐색하는 것이다.
  3. cnt < 공유기 개수: 거리를 줄여야 하기 때문에 왼쪽을 탐색한다.

package BinarySearch;

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

public class _2110_공유기_설치 {
    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 low = 1; // 최소 거리
        int high = houses[n-1] - houses[0]; // 최대 거리(첫 집 ~ 마지막 집)
        while (low <= high) {
            int mid = (high + low) / 2;

            int cnt = 1;
            int nowHouse = houses[0];
            for (int i = 1; i < n; i++) {
                if (houses[i] - nowHouse >= mid) {
                    cnt += 1;
                    nowHouse = houses[i];
                }
            }

            // 공유기 개수가 m이면서 가장 가까운 거리가 '최대'이길 원하기 때문에 cnt >= c일 때 오른쪽을 탐색(mid(최소거리)를 더 크게)한다.
            if (cnt >= c) low = mid + 1;
            else high = mid - 1;
        }
        System.out.println(high);
    }
}