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

문제

 

풀이

N의 범위가 20만, 집의 위치의 범위가 10억이므로 이분 탐색을 이용하여 풀어야 한다.

집의 개수가 아닌, 두 공유기 사이의 최대 거리에 초점을 맞춰 반복문마다 값을 수정해야 한다.

탐색하고자 하는 거리의 범위를 0부터 arr[N-1]로 설정하여 모든 값을 탐색할 수 있도록 한다.

최솟값과 최댓값의 평균을 탐색값으로 설정하고, 이 거리를 기준으로 몇 개의 공유기를 설치하는 지 검사한다.

이 값과 문제에서 주어진 공유기의 개수를 비교하여

이 값이 크거나 같다면(최대거리를 출력해야 하므로) 거리의 범위를 크게하고,

공유기의 개수가 크다면 거리의 컴위를 작게한다.

반복을 완료한 후 right 값을 출력하면 문제가 해결된다.

 

코드

 

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

class Main {
	
	public static void main(String[] args) throws IOException{
	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	StringTokenizer st;
    	st = new StringTokenizer(br.readLine());
    	
    	int N = Integer.parseInt(st.nextToken());
    	int M = Integer.parseInt(st.nextToken());
    	long arr[] = new long [N];
    	long total =0;
    	long min = 0;
    	for(int i=0;i<N;i++) {
    		arr[i] = Long.parseLong(br.readLine());    	    		
    	}
    	
    	Arrays.sort(arr);
    	long left = 0;
    	long right = arr[N-1];
    	
    	long now = 0;
    	long count=0;
    	
    	while(left<=right) {
    		    		
    	min = (left+right)/2;
    	now = 0;
    	count =1;
    	for(int i=1;i<N;i++) {
    		if(now+arr[i]-arr[i-1]<min)
    		{
    			now+=(arr[i]-arr[i-1]);
    		}
    		else {
    			now=0;
    			count++;
    		}
    		
    		
    		
    	}
    		if(count<M) {
    			right = min-1;
    		}
    		else left = min+1;

    		
    	}
    	bw.write(String.valueOf(right));
    	bw.flush();
    }
}

 

결과