백준 2110 (공유기 설치) - java

 

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

2110번: 공유기 설치

가능한 거리에 대해 이진탐색을 통해 해결하는 문제이다. 개인적으로 집(주어지는 값)에 대해 이분 탐색을 수행하는 방법을 고려했으나 해결법이 생각나지 않았다. 가능한 거리에 대해 이진탐색을 수행한다면 O(NlogN)안에 문제를 해결할 수 있다.

/*
*   백준 2110 (공유기 설치)
*   이분 탐색 : 기준이 뭘까?
*   기준 : 거리
* */
import java.io.*;
import java.util.*;
public class Main {
    static int n = 0;
    static int m = 0;

    static int result = 0;
    static int[] board;
    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());
        board = new int[n];
        m = Integer.parseInt(st.nextToken());
        for(int i=0;i<n;i++)
        {
            board[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(board);
        bs(1,board[n-1] - board[0]); // 가능한 거리의 최솟값 , 최댓값
        System.out.println(result);
        br.close();
    }

    static void bs(int left,int right)
    {
        while(left <= right)
        {
            int mid = (left + right) / 2;

            int count = 1;
            int idx = 0;
            for(int i=1;i<n;i++)
            {
                if(board[i] >= board[idx] + mid)
                {
                    count = count +1;
                    idx = i;
                } // 해당 거리마다 공유기를 설치

                if(count==m)
                    break;
            }
            
            // 조건을 만족하는 경우 , 결과값이 최댓값일 경우 갱신 , 하한 조정
            if(count >= m)
            {
                if(result < mid)
                    result = mid;
                left = mid + 1;
            }
            // 더 적은 개수일 경우 상한을 조정
            else{
                right = mid -1;
            }
        }


    }
}