[백준] 2110 공유기 설치 - Java

 

 

 

매개 변수 탐색을 활용해서 풀 수 있는 문제이다.

 

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 최대 거리를 구하시오.

=>

두 공유기 사이의 최대 거리를 적당히 설정했을 때 C개의 공유기를 설치할 수 있는지 구하시오.

 

 

공유기 C개를 설치할 수 있는지에 대한 확인은 그리디 느낌으로 일단 싹다 설치해놓고 C이상이면 true, 아니면 false를 반환하도록 작성했다.

 

 

매개 변수 탐색은 이분 탐색을 기반으로 함을 잊지 말자.

 

 

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

public class Main{	

	static int N;
	static int C;
	static int[] Home;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());

		Home = new int[N+1];

		for(int i=1; i<N+1; i++){
			Home[i] = Integer.parseInt(br.readLine());
		}

		Arrays.sort(Home, 1, N+1);

		BinarySearch();

		
	}

	static void BinarySearch(){
		int L = 1; int R = 1_000_000_000;
		int ans = 0;

		while(L <= R){
			int mid = (L + R) / 2;
			if(check(mid)){
				ans = mid;
				L = mid + 1;
			}else{
				R = mid - 1;
			}

		}

		System.out.println(ans);
	} // bs 

	static boolean check(int distance){
		int cnt = 1;
		int last = Home[1];

		for(int i = 2; i<N+1; i++){
			if(Home[i] - last < distance){
				continue;
			}
			// 일단 공유기 다 박아놓고 생각 마지막에 비교하면 됨

			last = Home[i];
			cnt++;
		}

		if(cnt >= C){
			return true;
		}else{
			return false;
		}

	}

}