[BOJ 2110] 공유기 설치

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.

둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

 

- '간격'을 기준으로 이분탐색. min값은 1이며, max값은 arr[n-1]이 된다.

- 핵심은 간격을 줄였다 늘였다를 반복하며 공유기를 C대 놓을 수 있는지!

    * Ex ) 공유기 4대를 놓아야한다. 최소 거리는 3이라 가정

    * 거리 3을 두고 공유기 4대를 놓을 수 있었다면 이진 탐색 개념에 의해 min = mid + 1 후 넣어본다.

    * 거리 3을 두고 공유기 4대를 놓을 수 없었다면 이진 탐색 개념에 의해 max = mid -1 후 넣어본다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String[] input = br.readLine().split(" ");
        
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        
        int[] arr = new int[n];
        
        for (int i=0; i<n; i++)
        {
        	arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);
        
        int min=1;
        int max = arr[n-1] - arr[0];
        while (min <= max)
        {
        	int mid = (min + max) / 2;
        	int cnt=1;
        	int standard = arr[0]; // 맨 처음에 놓는 것이 후보.
        	
        	for (int i=1; i<n; i++)
        	{
        		if (arr[i] - standard >= mid)
        		{
        			standard = arr[i];
        			cnt++;
        		}
        	}
        	
        	if (cnt >= m)
        	{
        		min = mid + 1;
        	}
        	
        	else
        		max = mid - 1;
        	
        }
        
        System.out.println(max);
    }
}