백준 2110 공유기 설치 (Python)

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

2110번: 공유기 설치

당연하게 이분 탐색으로 풀었다.

이분탐색을 푸는 루틴이 생긴 것 같다.

우선 함수를 만들고 그 함수를 기준으로 left 쪽으로 갈지, right 쪽으로 갈지 정하는 것이다.

 

이번 문제의 함수에서 반환하는 값은 공유기의 개수이다.

거리를 기준으로 공유기를 놓아보고, 만약 공유기가 더 필요하다면 거리를 늘리는 것이다.

 

import sys

N, M = map(int, sys.stdin.readline().split())

house = []

for i in range(N):
    house.append(int(sys.stdin.readline()))

house.sort()


def wifi(length):
    result = 1
    cur = house[0]
    for i in range(1, N):
        if house[i] >= cur + length:
            cur = house[i]
            result += 1

    return result


left = 1
right = house[-1] - house[0]

while left <= right:
    mid = (left + right) // 2
    cnt = wifi(mid)

    if cnt >= M:
        left = mid + 1
    else:
        right = mid - 1

print(right)