백준_2110_공유기 설치

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

2110번: 공유기 설치

해결 방법

> left, right에 각 최소, 최대거리를 설정한다.

> 처음 집에 공유기를 설정한 후 집과 집 사이의 거리에 대한 이분 탐색을 돌리며 공유기의 개수를 센다.

> 기준보다 공유기 설치수가 크다면 거리를 늘린다.(left = mid + 1)

> 작다면 거리를 좁힌다.(right = mid - 1)

 

코드

house, wifi = map(int,input().split())

 

_list = list()

for i in range(house):

    _list.append(int(input()))

 

_list.sort()

 

def check(mid):

    count = 1   #_list[0]에 공유기를 설치하고 시작하므로 1로 초기화

    now = _list[0]

    for i in range(1,len(_list)):

        if _list[i] - now >= mid:

            count += 1

            now = _list[i]

    if count >= wifi:

        return True

    else:

        return False

 

left, right = 1, _list[-1] - _list[0]   #최소거리, 최대거리

result = 0

while left <= right:

    mid = (left + right) //2

    if check(mid):

        result  = max(result,mid)

        left = mid + 1

    else:

        right = mid - 1

 

print(result)