[백준 2110] 공유기 설치 (JAVA)

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

2110번: 공유기 설치

 

이 문제는 2달전에 풀었던 문제인데, 오픈 채팅방에서 어떤 분이 아침부터 풀으셨다길래

한번 더 풀어보았다!

 

2달전의 코드와 비교해보니 더 간단하게 풀어버려서 은근 뿌듯하네 ㅎㅎ,,

제발 실력이 더 좋아져라 ㅠㅠㅠ!!

 

<풀이> 

이분 탐색으로 최소 거리의 값을 mid로 잡고 탐색한다.

mid값보다 크거나 같은 거리일 경우에는 공유기 설치 카운트를 +1한다.

그렇게 설치 카운트가 c보다 클 경우에는, 어차피 최소거리는 mid인 것이기 때문에 합격~

 

 

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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n=Integer.parseInt(st.nextToken());
		int c=Integer.parseInt(st.nextToken());
		
		int max=0;
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=Integer.parseInt(br.readLine());
			max=Math.max(arr[i], max);
		}
		
		Arrays.sort(arr);
		
	
		int result=0;
		int start=1;
		int end=max;
		while(start<=end) {
			int count=1;
			int prev=0;
			
			boolean check=false;
			int mid= (start+end)/2;
			for(int j=1;j<n;j++) {
				if(arr[j]-arr[prev]>=mid) {
					prev=j;
					check=true;
					count++;
				}
			}
			
			if(check&&count>=c) {
				start=mid+1;
				result=mid;
			}else {
				end=mid-1;
			}
		}
		
		System.out.println(result);
	}

}