[BOJ]2110 -공유기 설치(G4)

문제 링크

2110-공유기 설치

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.
둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

문제 풀이

이분탐색 문제는 오랜만인데
처음엔 약간 헤매다가 풀긴했는데
이게 맞나?라고 생각하면서 풀었다.

이후에 구글링하다보니 너무 정리가 잘 된 블로그 글이 있어서 마이구미님 블로그 참고

우선 특정 간격을 기준으로 가능한 위치에 공유기를 설치
공유기 수가 C보다 작으면 더 설치되어야하는거여서 간격을 줄이기
더 크다면 갯수를 줄여야하는거여서 간격을 늘리기

위의 로직을 반복하면 된다.

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

public class Main {
    static int N, C;
    static int[] house;

    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());

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

        int start = 1;
        int end = house[N - 1] - house[0];
        int result = 0;

        while (start <= end) {
            int mid = (start + end) / 2;
            int left = house[0];
            int cnt = 1;

			// 집집마다 검색
            for (int i = 1; i < N; i++) {
            
            	// 만약 첫번째 집과의 거리가 더 크다면 찾은거
                // cnt올려주고, 내가 찾는 집에 이번 집을 넣어줌
                if (house[i] - left >= mid) {
                    cnt++;
                    left = house[i];
                }
            }

            if (cnt >= C) {
                result = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        System.out.println(result);
    }

}