2110 공유기 설치

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

2110번: 공유기 설치

아이디어

1. list가 크기 때문에 전형적인 이분탐색 문제

2. 포인트는 "가장 인접한 두 공유기 사이의 거리" 이고 이를 코드에서는 mid 변수로 판단한다. (mid기준으로 공유기 설치가 C보다 많으면 이도 정답 후보군이 될 수 있음.)

3. 최댓값을 구하는 것을 지켜야 함

4. 공유기를 sorting 한 다음 탐색을 진행, 가장 첫번째 집에는 공유기를 설치하는 것이 많이 설치해야 하는 것을 생각한다면 유리하다.

if __name__ == "__main__":
    N, C = list(map(int, input().split(" ")))
    home = []
    res = 0

    for _ in range(N):
        home.append(int(input()))

    home = sorted(home)

    low = 1
    high = max(home)

    while True:
        if low > high:
            break

        mid = (low + high) // 2

        temp = home[0]
        cnt = 1

        for h in home[1:]:
            if h - temp >= mid:
                cnt += 1
                temp = h

        if cnt >= C:
            res = max(res, mid)
            low = mid + 1
        else:
            high = mid - 1

    print(res)