[백준 JAVA] 2110번: 공유기 설치

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

 

N개의 집에 C개의 공유기를 놓을 때 가장 인접한 두 공유기 사이의 거리가 최대로 하는 문제이다.

 

제한 조건: 
N <= 20만

C <= 20만

좌표 <= 10억

 

가장 간단하게 푼다면 경우의 수를 따져서 각각 공유기를 설치해본다음 거리를 계산하는 방법인데 시간복잡도가 nCc 이므로 너무 터무니없이 크다.

 

그래서 완전 다른 방법인 DP나 이분탐색, 투포인터로 사고를 전환했다.

 

하지만 고민해도 마땅한 방법이 떠오르지 않아서 GPT 한테 힌트를 달라고 요청했다.

 

이분탐색으로 풀어야한다는 말을 듣고 문제를 혼자 풀어보았다.

 

잘 안풀려서 보고 풀었다.

 

import java.io.*;
import java.util.*;

public class Main {
    static int N, C;
    static int[] x;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

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

        Arrays.sort(x);

        int l = 1;
        int r = x[N - 1] - x[0];
        int ans = 0;

        while(l <= r) {
            int m = (l + r) / 2;

            if(isValid(m)){
                ans = m;
                l = m + 1;
            }else{
                r = m - 1;
            }
        }

        System.out.println(ans);
    }

    static boolean isValid(int d){
        int count = 1;
        int last = x[0];

        for(int i = 1; i < N; i++){
            if(x[i] - last >= d){
                count++;
                last = x[i];
            }
        }

        return count >= C;
    }
}

 

 

이분탐색이 늘 헷갈린다. 보면 알겠는데 나중에 보면 또 모르겠다. 오늘은 일단 이 문제 푸는 방법을 이해했다는 걸로 넘어가자