*백준)공유기 설치

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

2110번: 공유기 설치

 

 

n, c = map(int, input().split())

array = []
for i in range(n):
    array.append(int(input()))

array.sort()


def binary_search(array, start, end):
    while start <= end:
        mid = (start + end) // 2
        current = array[0]
        count = 1

        for i in range(1, len(array)):
            if array[i] >= current + mid:
                count += 1
                current = array[i]

        if count >= c:
            global answer
            start = mid + 1
            answer = mid
        else:
            end = mid - 1


start = 1
end = array[-1] - array[0]
answer = 0

binary_search(array, start, end)
print(answer)

문제에서 요구한 것은 주어진 공유기의 개수를 충족하며 공유기가 벌릴 수 있는 최대거리를 구하는 것이다.

이 문제는 처음 봤을 때, 어떻게 이분법으로 푸나 굉장히 고민했었다.

늘 그렇듯 구글은 답을 알고있었고 이해하는데 조금 애를 먹었다.

mid는 공유기 사이의 거리이다.

초기의 start, end는 어떻게 잡나 상관이 없지만, 최소값과 최대값으로 잡는 것이 가장 효율적이다.

처음 미드값을 기준으로 공유기를 하나씩 설치한다.

처음 미드값이 4인경우, 배열을 하나씩 비교하며 이전 공유기의 거리가 4 이상이면 현재 공유기의 위치를 업데이트하고 count 를 +1시켜준다.

배열을 모두 돌았다면, count, 즉 설치된 공유기의 개수를 확인한다.

설치한 공유기가 입력값보다 작은 경우

즉, 거리를 줄여야 한다는 뜻이다.

예를들어, start = 1, end = 8, mid = 4일때, 

배열 중에서 첫번째는 무조건 설치되므로 1에 설치,

그리고 1과 4이상 떨어진 거리를 만족하는 요소는 8이다.

8보다 큰 수는 9이지만 8과 9는 4이상 차이나지 않으므로

mid가 4일때 최종적으로 설치된 공유기의 수는 2개, 1과 8이다.

현재 설치된 개수는 2개, 입력값은 3이므로 거리를 줄이므로 공유기의 설치를 늘릴 수 있다.

반대로 공유기가 입력값보다 많다면 거리를 좀 더 벌릴 수 있다는 뜻이다.