[백준] 2110. 공유기 설치 - Python

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

---

• 생각
  • 공유기 사이의 거리를 기준으로 이진탐색
  • start = 1, end = 첫번째 집과 마지막 집 거리
  • mid = (start + end)//2
  • 거리가 mid 이상이면 뽑기
    • 첫번째 집부터 순서대로 거리 계산
  • 만약 공유기 설치한 집 수가 원하는 집 수보다 적으면
    • mid를 줄여야함
  • 같다면
    • 가장 인접한 두 공유기 사이의 최대 거리를 구하는 것이므로 mid를 늘려야함
    • 정답이 될 수 있음
  • 크다면
    • mid를 늘려야함
    • 정답이 될 수 있음
• 코드

from sys import stdin
input = stdin.readline

# 집의 개수, 공유기의 개수
N, C = map(int,input().split())

# 집의 좌표
house = [int(input()) for _ in range(N)]
house.sort()

# 공유기 사이 최소거리, 최대거리
start = 1
end = house[-1]-house[0]

answer = 0
while start <= end:
    mid = (start+end)//2
    # 공유기 사이 거리를 최소 mid로 할 때 설치할 수 있는 공유기 개수 구하기
    # 시작점 house[0]
    current = house[0]
    cnt = 1
    for i in range(1,len(house)):
        # 다음 공유기까지 거리가 mid 이상?
        if house[i] >= current + mid:
            current = house[i]
            cnt += 1

    # 설치하고 싶은 공유기보다 더 적게 설치했으면 -> 거리를 좁히기
    if cnt < C:
        end = mid - 1
    else:
        start = mid + 1
        answer = mid
        
print(answer)