[BOJ]2110_공유기설치_Java

--문제--

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

2110번: 공유기 설치

--문제 접근--

공유기 설치 문제는 이분 탐색의 문제로 공유기를 설치하였을 때에 가장 큰 거리를 구하는 문제로 
여기서 주요할 점은 거리에 대해서 생각해보는 것이였습니다.
그래서 최대로 구할 수 있는 거리를 구해보고 그 거리에대해 계속적인 이분 탐색을 하면서 구하는 과정으로 생각해서 구해봤습니다.

package 백준문제풀이;

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

public class BOJ_2110_공유기설치 {
	//문제접근
	//공유기설치문제는 이분탐색의 문제로 공유기를 설치하였을때에 가장큰 거리를 구하는 문제로 
	//여기서 주요할 점은 거리에대해서 생각해보는 것이였습니다.
	//그래서 최대로 구할 수 있는 거리를 구해보고 그 거리에대해 계속적인 이분탐색을 하면서 구하는 과정으로 생각해서 구해봤습니다.
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb=new StringBuilder();
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int C=Integer.parseInt(st.nextToken());
		int[] arr=new int[N];
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		Arrays.sort(arr);
		long start=1;
		long end=arr[N-1]-arr[0];
		long mid=0;
		long ans=0;
		while(start<=end) {
			mid=(start+end)/2;
			int cnt=1;
			long install=arr[0];
			for(int i=1;i<N;i++) {
				if(arr[i]-install>=mid) {
					cnt++;
					install=arr[i];
				}
			}
			if(cnt>=C) {
				ans=mid;
				start=mid+1;
			}
			else end=mid-1;
		}
		sb.append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
		
	}
}