[알각코] 인프런 4-4 마구간 정하기 (결정알고리즘)

마구간 정하기 (결정알고리즘)

문제 정보는 인프런의 파이썬 알고리즘 문제풀이 코딩테스트에 있습니다!

문제풀이

import sys
sys.stdin = open("input.txt", "r")
def count(len):
  cnt = 1
  ep=house[0]
  for i in range(1, n):
    if house[i]-ep>=len:
      cnt+=1
      ep=house[i]
  return cnt

n, c = map(int, input().split())
house = []
for i in range(n):
  house.append(map(int, input()))

house = sorted(house)
lt = 1
rt = house[n-1]
res = 1

while lt <= rt:
  mid = (lt+rt)//2
  if count(mid)>=c:
    res=mid
    lt=mid+1
  else:
    rt=mid-1

print(res)