BOJ 2110 공유기 설치

해당 문제는 이분 탐색을 활용한 문제이다. 

 

1. 이분탐색을 통해 간격을 찾는다. 여기서 간격은 mid값으로 구할 수 있다. 

( left 값은 1, right값은 첫번째 집과 마지막 집 사이의 거리로 정해놓는다.)

2. 간격을 좁혀야하면 ( 해당 간격에서는 공유기를 c개수만큼 못 놓는다면 ) 범위를 왼쪽으로 줄여준다 ( right를 조정) -> mid 값이 작아짐 

3. 간격을 넓혀도 되면 (해당 간격에서 공유기를 c개수만큼 or 그 이상 놓을 수 있다면) 범위를 오른쪽으로 넓힌다 (left조정)  -> mid 값이 넓어짐

 

결국 마지막 cnt>=c 일 때의 mid 값이 최대 간격이 된다. 

import java.util.*;
public class Main {
	static int[] house;
	public static void main(String[]args) 
	{
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		house=new int[n];
		int c= sc.nextInt();
		for(int i=0; i<n; i++) 
		{
			house[i]=sc.nextInt();
		}
		
		Arrays.sort(house);
		System.out.println(solution(n,c));
	}
	
	public static int solution(int n, int c) {
		
		int left =1;
		int right = house[n-1]-house[0]; // 맨 처음 집과 끝집 사이의 길이  
		int mid =0;
		int result =mid;
		
		while(left<=right) 
		{
			mid = (left + right) / 2; 

			int start = house[0]; //처음 공유기를 놓는 곳 
			int cnt = 1;
			for(int i=1; i<n; i++) { // house 배열을 돌아가며 공유기를 놓을 수 있는지 살펴본다. 
				if(house[i]-start >= mid) { //공유기를 놓을 수 있음 
					cnt ++; //공유기 놓는다. 
					start = house[i]; //공유기 놓은 기준 바꾸기 
				}
			}
			
			if(cnt >= c) { // 정해진 공유기 개수보다 많이 놓았다면 넓이를 더 넓혀도 된다. 
				//결국 가장 마지막 루프의 cnt값이 최대로 놓을 수 있는 공유기의 개수가되고,
				//해당 공유기를 놓을 때 집사이의 거리가 가장 인접한 두 집 사이의 가장 넓은 간격이 된다. 
				result =mid;
				left=mid+1;
			}
			else { //정해진 공유기의 개수보다 적게 놓았다면 넒이를 좁혀야한다. 
				right=mid-1;
			}
		}
		return result;
	}
}