[백준] 2110번: 공유기 설치 - 파이썬(python)

문제

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

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

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

입력

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

출력

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

예제 입력 1 

5 3
1
2
8
4
9

예제 출력 1 

3

 

 

나의 풀이

import sys
input = sys.stdin.readline

N, C = map(int,input().split())
array = [int(input()) for _ in range(N)]
array.sort() # 오름차순 정렬

start = 1 # 모든 집은 다른 좌표에 있으므로 최소 공유기 거리는 1
end = array[-1] - array[0] # 최대 공유기 거리는 맨 끝 집 - 맨 첫 집
answer = 0

while start <= end :
  cur = array[0]
  cnt = 1 # 항상 1번째 집에 공유기를 설치
  mid = (start+end) // 2
  for i in range(1,N) :
    if array[i] - cur >= mid :
      cnt += 1
      cur = array[i] # i번째 인덱스에 공유기 설치
  if cnt >= C :
    if answer < mid : 
      answer = mid
    start = mid + 1
  else :
    end = mid - 1

print(answer)

이런 문제는 무엇을 기준으로 이분탐색을 하는지 아는 것이 중요하다..!

여기서는 가장 인접한 두 공유기 사이의 최대 거리를 mid 로 설정하여, 이분 탐색을 진행하는 것이 포인트다.

모든 집은 다른 좌표에 있으므로 start 는 1, end 는 (가장 멀리 있는 집 - 첫 집) 기 될 것이다.

array 를 오름차순 정렬했기 때문에, 가장 첫번째 집에는 항상 공유기를 설치해야 한다!! 그래야 가장 인접한 두 공유기 사이의 거리가 최대가 될 수 있기 때문이다.

 

따라서 첫 집에 공유기를 설치하고, 2번째 집부터 마지막 집까지 탐색을 하며첫 집과 현재 집의 거리가 mid 이상이라면? 해당 집에 설치를 하고, 기준이 되는 집을 현재 집으로 변경한 후 계속 탐색한다.mid 이상이 될 수 있는 거리에 모든 집을 설치한 후, 설치한 공유기 개수가 C 이상이라면answer 값을 갱신하고, start 를 mid+1 로 변경하여 다시 반복한다.

C보다 작다면 mid 값이 너무 큰 것이므로 end 를 mid-1로 변경하여 다시 반복한다.