[백준] 이분 탐색 - 2110번 공유기 설치 java

문제

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

2110번: 공유기 설치

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

풀이

right와 left를 각각 설치 가능한 최대 거리, 최소 거리로 두고 집마다 거리를 계산하여 공유기 설치가 가능하다면 cnt를 증가시킨다.

이때 cnt가 C보다 크거나 같다면 공유기 수를 줄여야 하는 것이므로 간격을 늘이고 그렇지 않다면 공유기 수를 늘려야 하는 것이므로 간격을 줄인다.

 

코드

package 이분탐색;

import java.util.*;
public class No2110_공유기설치 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		int C=sc.nextInt();
		
		int[] x=new int [N];
		for(int i=0;i<N;i++) {
			x[i]=sc.nextInt();
		}
		Arrays.sort(x);
		
		int right=x[N-1]-x[0]; //가능한 최대 거리 
		int left=1; //가능한 최소 거리 
		int mid=0;
		int d=0; //거리 계산 
		int ans=0;
		
		while(left<=right) {
			mid=(right+left)/2; // 비교 기준 
			int start=x[0];
			int cnt=1; // 설치 되는 공유기 개수 
			
			for(int i=0;i<N;i++	) {
				d=x[i]-start; //거리계산 
				if(d>=mid) { //공유기 설치 가능 여부 체크 
					cnt++;
					start=x[i];
				}
			}
			
			//공유기 수를 줄여야한다면 간격을 늘림 
			if(cnt>=C) {
				ans=mid;
				left=mid+1;
			}
			//공유기 수를 늘려야한다면 간격을 줄임 
			else {
				right=mid-1;
			}
		}
		
		System.out.println(ans);
	}

}