Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

21. 이분 탐색

이분 탐색 알고리즘을 배워 봅시다.

Java / Python

5. 공유기 설치

2110번

이분 탐색을 응용하여 최솟값이나 최댓값을 찾는 문제 3

이번 문제는 c개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하는 문제입니다.

• Java

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        
		int N = sc.nextInt();
		int C = sc.nextInt();
		int[] arr = new int[N];

		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();

		}
		Arrays.sort(arr);
		int left = 1; 
		int right = arr[N - 1] - arr[0];
		int d = 0;
		int result = 0;
        
		while (left <= right) {
			int mid = (left + right) / 2;
			int start = arr[0];
			int cnt = 1;
			for (int i = 0; i < N ; i++) { 
				d = arr[i] - start;
				if( d >= mid ){
					cnt++;
					start = arr[i];
                }
			}
			if (cnt >= C) { 
				result = mid;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		System.out.println(result);
	}
}

• Python

import sys
N, C = list(map(int, sys.stdin.readline().split()))
arr = []
for _ in range(N):
    arr.append(int(sys.stdin.readline()))
arr.sort()
start = 1
end = arr[-1] - arr[0] 
result = 0

while start <= end: 
    mid = (start + end) // 2 
    tmp = arr[0]
    cnt = 1
    for i in range(0, N):
        if arr[i] >= tmp + mid:
            cnt += 1
            tmp = arr[i]
    if cnt < C:
        end = mid - 1
    else:
        start = mid + 1
        result = mid
print(result)