[백준(Baekjoon)][자바(java)] 2110 : 공유기 설치 / 이분 탐색

 

www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), c = sc.nextInt();
		int x[] = new int[n], i;
		for( i = 0; i < n; i++ )
			x[i] = sc.nextInt();
		sc.close();
		
		Arrays.sort(x);				// x 좌표 오름차순 정렬
		
		int low = 1, high = x[n-1]-1, res = 0, mid, limit, cnt;
		while( low <= high ) {		// 최대 간격을 이분법으로 줄여나감
			mid = ( low + high ) / 2;
			limit = 0;
			cnt = 0;
			for( i = 0; i < n; i++ ) {	// 모든 공유기 간의 간격이 mid 이상 되는가
				if( limit <= x[i] ) {
					cnt++;
					limit = x[i] + mid;
				}
			}
            // 모든 간격이 mid 이상 이고 c만큼 설치할 수 있는가
            // 이분 탐색하며 최소 간격 mid를 최대화함
			if( cnt >= c )	 low = mid + 1;
			else		 	high = mid - 1;
		}
		res = low-1;
		
		System.out.println( res );
		
	}
}

( 출처 : 책 '알고리즘 문제 해결 전략' )

 

-  배열 x에 공유기 간 거리 입력받음.

-  배열 x 오름차순 정렬

-  두 공유기 간 사이의 거리는 최소 1, 최대 x_max-1

   이 구간의 값을 이분탐색으로 범위를 줄여가며 가장 긴 제일 인접한 거리를 구함