[백준/이진탐색] 2110번 공유기 설치

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

 

문제

• N개의 집이 있고, 좌표가 주어진다.
• C개의 공유기를 설치하여 최대한 많은 곳에서 와이파이를 사용하려고 한다.
• 공유기는 한 집에 하나만 설치할 수 있다.
• 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치한다.

 

출력

가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

풀이

• 거리를 이분 탐색하면 된다.
• 시작할 때 최소 거리는 바로 옆집이므로 1 이고, 최대 거리는 주어진 좌표의 끝과 끝이다.
• 현재 집에서 중간 거리 ((최소 + 최대) // 2) 보다 큰 집에 공유기를 설치한다.
• 중간 거리에 대해 공유기를 설치한 것이 보유한 공유기 (C) 보다 더 많은 경우, 거리를 더 줄여야 한다.
  반대로 공유기를 더 적게 사용한 경우 거리를 더 늘려도 된다.

 

코드

from sys import stdin

input = stdin.readline

N, C = map(int, input().split())

house = [int(input()) for _ in range(N)]
house.sort()

start, end = 1, (house[-1] - house[0])
result = 0

while start <= end:
    mid = (start + end) // 2
    cur = house[0]
    count = 1

    for i in range(1, N):
        if house[i] >= cur + mid:
            count += 1
            cur = house[i]

    if count >= C:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)