[이코테] 이진 탐색_공유기 설치 (python) (다시 풀어보자)

문제

나의풀이

1. 이진 탐색

아이디어

: 분명 아이디어는 간단한데, 의외로 이해하기까지 꽤 걸렸다.

• 전형적인 이진 탐색 알고리즘에서 중간값을 공유기 사이의 간격으로 잡는다.
• 중간값을 조정한다.
  • 설치된 공유기 수가 적다면, 간격을 줄인다.
  • 설치된 공유기 수가 많다면, 간격을 늘린다.

import sys
input = sys.stdin.readline

n, c = map(int, input().split()) # n: 집 개수, c: 공유기 개수
house = sorted(int(input()) for _ in range(n)) # 집 list

answer = 0 # 정답 초기화

start = 1
end = house[n - 1] - house[0] # 집 간의 최대 간격

while start <= end: # 더이상 나눌 수 없는 범위일 때 까지
    mid = (start + end) // 2 
    cnt = 1 # 공유기 설치 개수
    set_up = house[0] # 공유기 설치: 첫번째 집에는 무조건 설치
        
    # 우선, 간격 = mid로 공유기를 설치해보자
    # 다 설치한 다음에 공유기 수와 간격을 조정할 것이다
    for i in range(1, n):
        if house[i] - set_up >= mid: # 공유기 사이 간격이 mid 이상이면
            cnt += 1 # 공유기를 더 설치한다
            set_up = house[i]
            
    # 이제 공유기 수와 간격을 조정해보자
    if cnt >= c: # 공유기를 너무 많이 설치했으면
        start = mid + 1 # 간격을 늘리자
        answer = mid # 공유기를 c개 설치했을 때 최대거리 mid로 정답에 저장
    else: # 공유기를 너무 적게 설치했으면
        end = mid - 1 # 간격을 줄이자
            
print(answer)

• sys 아니면 시간초과남 ㅠ
• 부등호에서 왜 포함을 해야하는지 아직 잘 이해가 안간다. 그냥........하니까 정답이어서 했을 뿐.........