문제 링크

공유기 설치

문제 설명

집 N개가 수직선 위에 있을때, 최대한 많은 곳에서 와이파이를 사용할 수 있도록 공유기를 C개 설치한다. 한 집에는 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 설치한다.

IN
N C 집의 개수, 공유기의 개수
x1
x2
... 집의 좌표값 N개
OUT
가장 인접한 두 공유기 사이의 최대 거리

제약
집의 좌표는 1이상 10억 이하 -> 탐색범위가 10억이므로 이분탐색을 사용한다

문제 풀이

이 문제의 포인트는
1. 탐색범위가 10억이므로 이분탐색을 사용
2. 이분탐색할 대상이 가장 인접한 두 공유기 사이 거리

이분탐색의 대상을 처음에 설치할 위치로 두고 탐색해서 많이 헤메었다.. 이분탐색을 할 대상은 설치 위치가 아닌 gap의 크기임!

1. 가장 인접한 두 공유기 사이의 거리(이하 gap)의 최댓값을 찾아야 하므로
   gap을 최소 갭(house[1]-house[0]) ~ 최대갭(house[-1]-house[0])의 범위 내에서 이분탐색을 한다.
2. 현재 찾은 gap을 기준으로 실제 router를 몇개 배치할 수 있는지 본다. C개 이상이면 현재 값을 저장하고 gap을 늘려서 다시 탐색한다.

코드

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
houses = []
for _ in range(N):
    x = int(input())
    houses.append(x)
houses.sort()

# 이분탐색의 대상 : 가장 인접한 두 공유기 사이의 거리
start = houses[1] - houses[0]
end = houses[-1] - houses[0]

while start <= end:
    #현재 가장 인접한 두 공유기 사이의 거리 찾기
    gap = (start + end) // 2
    value = houses[0]
    count = 0

    #실제로 공유기 배치하기
    for house in houses:
        #설치가능하면
        if house >= value + gap:
            value = house
            count += 1

    #C개 이상의 공유기 설치할 수 없으면 거리 감소
    if count < C:
        end = gap - 1
    #C개 이상의 공유기 설치 가능
    else:
        start = gap + 1
        result = gap
print(result)

어렵넵,, 다시 풀어봐야겠다