[백준] 2110 - 공유기 설치

[문제링크]

2110번: 공유기 설치

 

0. 집에 n개의 공유기를 설치할 때, 가능한 최대 거리를 구하는 문제

  - 집 사이의 간격에 대해 바이너리서치 진행

 

1. 바이너리 서치의 시작점은 0, 끝점은 가장 먼 집의 좌표

 

2. 구한 dis에 따라, 최대한 그리디하게 집에 공유기를 설치했을 때의 갯수를 센다

 

3-1. 공유기가 목표 갯수를 충족했다면, ans를 갱신 후 min값을 갱신, 더 큰 dis를 시도해본다

3-1. 공유기가 목표 갯수에 미달했다면, max값을 갱신, 더 작은 dis를 시도해본다

 

4. min과 max가 교차하면 종료, 구한 ans값을 출력한다 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());
		int[]house = new int[n];
		for (int i = 0; i < n; i++) {
			house[i]=pint(br.readLine());
		}
		Arrays.sort(house);
		
		int min=0, max=house[n-1];
		int ans=0;
		while(min<=max) {
			int dis = (max+min)/2;
			
			int prev_house = house[0];
			int cnt=1;
			for (int i = 0; i < n; i++) {
				if(prev_house + dis <= house[i]) {
					prev_house=house[i];
					cnt++;
				}
			}
			if(cnt>=m) {
				ans=dis;
				min=dis+1;
				
			}else {
				max=dis-1;
			}
		}
		System.out.println(ans);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면