백준 2110번 "공유기 설치"

문제

백준 2110번 공유기 설치

풀이

전에 풀었던 이분탐색보다 좀 더 어려웠던 문제.
공유기를 설치할 수 있는 최소거리와 최대거리를 가지고 시작하여
중간값을 통해 특정 거리를 두고 얼만큼의 공유기를 설치할수 있느냐를 알아내어야 한다.
공유기 설치 숫자에 따라서 다른 이분탐색 문제와 같이 최대값과 최소값을 조정하여 반복을 하면 된다.

Python 코드

import sys
input =sys.stdin.readline

n, c = map(int, input().split())
x = sorted([int(input()) for _ in range(n)])

min_gap = 1
max_gap = x[-1] - x[0]

while min_gap <= max_gap:
  gap = (min_gap+max_gap)//2
  installed = x[0]
  cnt = 1

  for a in x[1:]:
    if a >= installed + gap:
      installed = a
      cnt+=1
    
  if cnt >= c:
    min_gap = gap + 1
    answer = gap
  else:
    max_gap = gap - 1

print(answer)