[백준] 2110. 공유기 설치

문제

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

2110번: 공유기 설치

 

설계

- 보통 이분탐색은 최소한의 횟수로 목표를 찾는 것이다.

- 이번 문제는 공유기를 설치할 거리를 이분 탐색으로 결정하여 공유기 사이의 거리가 mid값 이상인 경우 공유기를 설치할 수 있다.

- mid값 이상의 간격으로 공유기를 설치했을 때 공유기의 개수가 모자라다면 mid 값을 줄여주고, 설치해야하는 공유기의 개수가 너무 적다면 mid값을 높여준다.

N, C = map(int, input().split())
arr = [int(input()) for _ in range(N)]
start, end = 0, max(arr)
arr.sort()      # 주어진 숫자는 집들의 좌표이므로 정렬해준다.
answer = 0

while start <= end:
    mid = (start + end) // 2
    install = arr[0]    # 공유기를 설치한 위치
    cnt = 1     # 공유기를 하나 설치했으므로 1로 시작
    for i in range(N):
        if arr[i] - install >= mid:     # 공유기를 설치한 위치보다 거리가 클 경우 설치
            install = arr[i]        # 공유기를 설치한 최신 위치 갱신
            cnt += 1
    if cnt >= C:    # 설치해야 하는 공유기만큼 설치했다면
        answer = mid
        start = mid + 1
    else:
        end = mid - 1
print(answer)