[백준] 2110번 공유기 설치 파이썬 코드

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
house = [int(input()) for _ in range(n)]
house.sort() # 오름차순 정렬

start, end = 1, 1000000000 # 범위 지정. house[-1] - house[0]으로 해도 된다.
result = 0 # 결과를 저장할 변수
while start <= end:
  mid = (start + end) // 2
  gongu = 1
  location = house[0] # 첫 집에 설치. 
  					  # 거리를 최대로 해야하다보니 일단 첫 집에 하나 두고 시작.
  
  for i in house:
    if location + mid <= i:
      location = i     # 조건을 만족하는 집에 설치
      gongu += 1
    if gongu >m: break # 공유기 설치 개수가 넘어가면 for문 탈출.
    				   # 시간 아끼는 거에 도움이 될까싶어 넣음
  
  if gongu >= m: # 공유기 개수가 많으면 공유기 사이 거리를 늘려야함. 따라서 start = mid + 1
    start = mid + 1
    result = mid
  elif gongu < m: # 공유기 개수가 적으면 공유기 사이 거리를 줄여야 함. 따라서 end = mid - 1
    end = mid - 1
    
print(result)