공유기 설치 백준 2110번 이진탐색

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

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, …, xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

문제는 가장 인접한 두 공유기 사이의 거리의 최댓값을 탐색하는 문제로 이해할 수 있습니다. 각 집의 좌표가 최대 10억(탐색범위가 10억)이므로 모든 경우의 수를 찾을 수는 없습니다. 이진탐색을 사용해야하는데 가장 인접한 두 공유기 사이의 거리를 조절하면서 매 순간 실제로 공유기를 설치해서 C보다 많은 개수로 공유기를 설치할 수 이는지 체크하면서 문제를 해결해나가야 합니다.

먼저 가장 인접한 두 공유기 사이의 거리의 최댓값을 찾아야 하므로 C보다 많은 개수로 공유기를 설치할 수 있다면 가장 인접한 두 공유기 사이의 거리 값을 증가시켜서 더 큰 값에 대해서도 성립하는지 체크하기 위해 다시 탐색을 수행합니다.

#집의 개수(N)와 공유기의 개수(C)를 입력받기
n, c = list(map(int, input().split(' ')))

#전체 집의 좌표 정보를 입력받기
array = []
for _ in range(n):
    array.append(int(input()))
array.sort() #이진 탐색 수행을 위해 정렬 수행

start = array[1] - array[0] #집의 좌표 중에 가장 작은 값
end = array[-1] - array[0] #집의 좌표 중에 가장 큰 값

while(start <= end):
    mid =(start + end)//2 #mid는 가장 인접한 두 공유기 사이의 거리(gap)를 의미
    value = array[0]
    count = 1
    #현재의 mid값을 이용해 공유기를 설치
    for i in range(1,n): #앞에서 부터 차근차근 설치
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c: #C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가
        start = mid + 1
        result = mid #최적의 결과를 저장
    else:
        #C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소
        end = mid - 1

print(result)

입력하는 부분을 제외하고 start와 end 부터 봅시다.

시작하는 지점은 갭이 가장 작은 곳 마지막 지저믄 갭이 가장 큰 곳입니다.

예시에서는 갭은 1부터 8까지 입니다. 이제 여기서 이진 탐색을 시작하게 됩니다.

1의 8사이는 4가 됩니다. 그리고 앞에서 부터 설치를 쭉 해보기 시작합니다.

설치를 끝냈습니다. 공유기를 더 설치할 수 있는가 없는가로 판단을 해봅시다.

거리를 4로 두었을때 설치할 수 있는 공유기는 2개입니다. 그런데 예제에서는 3개를 설치할 것을 요구하니 공유기간 거리를 더 줄여보겠습니다. 1에서 4까지 였으니 절반 지점인 2를 선택합시다. 그러면 공유기는 3개를 설치를 할 수 있지만 조건에서 거리를 최대한 벌려서 설치를 하고 싶다는 조건이 있습니다.

그래서 아직 남은 탐색범위인 [2,3]에서 거리가 3인지도 확인을 해줍시다. 마찬가지로 3일때도 공유기를 3대 설치를 할 수 있고 이를 넘어가면 start와 end가 바뀌는 지점이기 때문에 서칭을 종료를 하고 거리 3을 반환합니다.