[BOJ 2110] 공유기 설치 (Java, Python)

문제

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

2110번: 공유기 설치

 

풀이

이분 탐색을 이용하여 풀 수 있다.

처음에 문제를 이해하는데 시간이 걸려서, 최대한 자세히 풀이를 써보려고 한다.

 

예제는 다음과 같다.

집의 개수 : 5개, 공유기 개수: 3개 

5 3
1
2
8
4
9

여기서 구해야 할 것은?? 가장 인접한 두 공유기 사이의 최대 거리를 출력하는 것이다.

 

아래와 같이 집이 위치해있다고 가정했을 때,

 

 

가장 인접한 두 공유기 사이의 거리를 1로 가정한다면?

아래와 같이 3개를 설치할 수 있다.

 

가장 인접한 두 공유기 사이의 거리를 8로 가정한다면?

아래와 같이 2개를 설치 할 수 있다. (3개 설치 불가능)

 

여기서 우리가 원하는 건 공유기 3개를 모두 설치하면서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 것이다. 

때문에 전자의 경우는 인접 거리를 늘려서 탐색을 할 필요가 있고, 후자의 경우는 인접 거리를 줄여서 탐색을 해야 한다.  

 

이 때, 가장 인접한 두 공유기 사이의 최대 거리를 이분탐색을 이용해 찾는다. 

 

 

최초의 처음과 끝을 아래와 같이 정의한다.

• 최소로 인접한 두 공유기 사이의 거리: 집과 집 사이의 최소 간격이 1이므로 1이 된다. 
• 최대로 인접한 두 공유기 사이의 거리: 첫 번째 집과 마지막 집의 간격이 된다. 8

아래 내용으로 이분 탐색을 하며 해당 거리로 공유기가 설치 가능한지 체크하면서 최대 거리를 찾아나간다. 

• 공유기를 모두 설치하는 것이 불가능하면 하면 인접 거리를 좁혀서 재탐색한다. 
• 공유기가 모두 설치 되었다면 인접 거리를 늘려 재탐색 한다.

 

첫 번째 탐색

left: 1, right: 8, mid: 5

두 공유기 사이의 거리가 5일 때? 

3개 설치 불가능 하므로 right를 mid - 1로 갱신하여 재 탐색한다.

두 번째 탐색

left:1, right: 4, mid: 2

두 공유기 사이의 거리가 2일 때?

3개 설치가 가능하므로, left 를 mid +1 로 갱신하여 재 탐색한다.

세 번째 탐색

left:3, right:4, mid: 3

두 공유기 사이의 거리가 3일 때?

3개 설치 가능, left를 mid + 1로 갱신하여 재 탐색한다. 

네 번째 탐색

left:4, right:4, mid: 4

두 공유기 사이의 거리가 4일 때?

설치 불가능, right를 mid -1 로 갱신하면서 left보다 작아지므로 이분탐색이 종료된다.

 

가장 인접한 두 공유기 사이의 최대 거리는 세번 째 탐색의 mid값이 된다.

소스코드는 아래와 같다. 

 

소스코드

package binarysearch;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ2110 {

    public static void main(String[] args) throws Exception {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 좌표의 수
        int C = Integer.parseInt(st.nextToken()); // 공유기의 수

        int[] houses = new int[N];
        for(int i = 0; i < N; i++){
            houses[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(houses);

        int left = 1; // 최소 인접 거리
        int right = houses[N-1] - houses[0]; // 최대 인접 거리

        int result = 0;
        while(left <= right){
            int mid = (left + right)/2;
            if(getPossibleCnt(houses, mid) >= C){
                // 공유기 더 많이 설치된다. 인접 거리 더 늘리자.
                result = Math.max(result, mid);
                left = mid+1;
            } else {
                // 공유기 설치 불가능. 인접 거리를 좁혀야 함.
                right = mid-1;
            }
        }

        System.out.println(result);

    }

    public static int getPossibleCnt(int[] houses, int diff){
        // 해당 인접 거리로 공유기 설치 시 가능한 설치 개수
        int possibleCnt = 1;
        int prev = houses[0];
        for(int i = 0; i < houses.length; i++){
            if(houses[i] - prev >= diff) {
                prev = houses[i];
                possibleCnt++;
            }
        }
        return possibleCnt;
    }
}

 

Python

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))

arr.sort()

def get_possible_count(array, distance):
    count = 1
    prev = array[0]
    for i in range(1, len(array)):
        if array[i] - prev >= distance:
            prev = array[i]
            count += 1
    return count

def binary_search(start, end, array):
    global c
    result = 0
    while start <= end:
        mid = (start+end)//2
        if get_possible_count(array, mid) >= c:
            start = mid + 1
            result = mid
        else:
            end = mid - 1

    return result

print(binary_search(1, arr[n-1]-arr[0], arr))