공유기 설치 - 2110번

문제

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

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

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

입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

풀이

처음엔 집 좌표 위치를 모두 합해서 N으로 나누면 그게 맞는 거리값이 될 줄 알았다. print( (min(places)+max(places))//C ) 이렇게 말이다.
그래서 왜 이분탐색 문제인지도 이해가 안 됐었는데, 이 풀이는 곧 집의 좌표들이 [ 1,2,3,...9 ]와 같이 1의 간격으로 순차적인 경우에만 가능한 풀이였고, 특정 숫자로 집의 좌표가 주어진 이 문제에서는 적절치 않은 문제 해석이었던 것이다.

이 문제의 접근법은 이러하다.

먼저, 입력으로 주어진 집의 위치를 오름차순으로 정렬한다. 그리고 이분 탐색을 통해 공유기 사이의 거리를 조정해나가면서, 공유기를 최대한 많이 설치하는 경우를 찾았다.

공유기 사이의 거리를 이분 탐색하기 위해서는, 가능한 최소 거리와 최대 거리를 초기 값으로 설정하고, 중간 값(mid)을 계산한 후, 이를 기준으로 공유기를 설치하는 경우를 계산한다. 만약 설치된 공유기의 개수가 C개보다 작으면, mid값을 감소시키고, C개 이상이면 mid값을 증가시킨다.

--> 이 과정을 최소 거리와 최대 거리가 교차할 때까지 반복하는 것이다.

아래의 답은 정답이다.

import sys
input = sys.stdin.readline
N, C = input().split()
N = int(N)
C = int(C)
places = sorted(list(int(input()) for _ in range(N)))
placerange = places[1:]

# print( (min(places)+max(places))//C ) # wrong. 집의 좌표들이 1,2,3,...9인 경우에만 가능한 얘기.

result = 0

def binary_search(min, max):
    global result
    while min <= max:
        mid = (min+max)//2
        cnt = 1
        curr = places[0]
        for i in placerange:
            if i - curr >= mid:
                cnt += 1
                curr = i
        if cnt >= C:
            min = mid + 1
            result = mid
        else:
            max = mid - 1
    return result

print(binary_search(1, places[-1]-places[0])) # == (집과 집 간의 최소 거리, 최대 거리) == (1, max(places)-min(places))

그래서 나같은 경우에는 이걸 어떻게 했냐면, sorted()해서 오름차순이 된 집의 좌표들 중 맨 첫번째 즉 그래프 상 가장 왼쪽에 위치한 집의 좌표를 변수 cur로 따로 뺐다. 또, 전체 집의 좌표 리스트 중 cur가 제외된 리스트 placerange를 따로 뺐다.
이는 왜냐하면 탐색의 첫번째 지점이 언제나 첫번째 집이기 때문이다.
그래서.... 탐색하는 for문 작성 시, 리스트 place의 두번째 요소부터 끝까지를 for문으로 돌린다. placerange = places[1:]
다시 말해 현재 설치할 집의 위치 변수 curr는 처음이 언제나 첫 집 좌표 place[0]인 거고, 말인즉 for문의 시작은 다음과 같게 된다.

• 1. "두번째 집 좌표 i" - "첫 집 좌표 curr"가 mid보다 크면, 두번째 집에 공유기 설치가 가능한 거다. 그럼 갯수카운터 cnt을 +1 하고 curr를 i로 갱신한다.
• 2. "두번째 집 좌표 i" - "첫 집 좌표 curr"가 mid보다 작다면, 이는 거리를 나타내는 mid값보다 두 집 간의 거리가 좁단 뜻이므로 두번째 집에 설치하지 못한다는 뜻이 된다. 그럼 for문의 조건문으로 다시 복귀하여 세번째 집 좌표가 들어오게 되고,

--> 그런 식으로 거리값 mid를 둔 채 주어진 집마다 공유기를 설치해보는 식으로 for문이 도는 것.

그래서...
거리값 mid일 때 설치할 수 있는 공유기의 숫자가

• 1. C개 이상일 때에는 mid값 기록 후 탐색을 mid보다 1 큰 수 부터 최댓값까지,
• 2. C개 미만일 때에는 탐색을 1부터 mid보다 1 작은 수까지,
     탐색 범위를 재조정하여 재탐색하는 것이다.

탐색이 끝나면 즉 while문에서 탈출하면 변수 result에 기록되어 있던 최신 거리값 mid를 return한다.