Baekjoon Online Judge 2110번 파이썬

문제 링크
https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

mid의 값을 간격으로 공유기를 설치한다. 만약 공유기의 개수가 N보다 크면, start를 mid+1로 하여 간격을 넓힌다. 만약 공유기의 개수가 N보다 작으면, end를 mid-1로 하여 간격을 좁힌다.
가장 인접한 공유기의 거리를 최대로 하는 결과를 출력해야하기 때문에 end의 값을 출력해야한다.
5 3 / 1 6 7 8 9 의 테스트에서, start를 loc[1] - loc[0]으로 두면 프로그램은 5~8만 검사하게 된다. 그래서 정답인 2는 찾을 수 없다. 경우에 따라 loc[1]-loc[0]은 최단 거리가 아닐 수도 있다. 그래서 start를 1로 두어야 한다.

정답 코드

import sys

N, C = map(int,sys.stdin.readline().split())
loc = []
for i in range(N):
  loc.append(int(sys.stdin.readline()))
loc = sorted(loc) #편의를 위해 배열 정렬

start = 1 #최단 거리
end = loc[N-1] - loc[0] #최장 거리

while start <= end:
  mid = (start + end) // 2
  count = 1 #첫번째 원소를 기준으로 먼 집을 찾기 때문에 count를 1로
  current = loc[0]
  for i in range(1,len(loc)):
    if loc[i] >= current + mid: #설치할 집 찾기.
      count += 1
      current = loc[i]
  if count >= C:
    start = mid + 1
  else:
    end = mid - 1

print(end)