[백준] 2110번 - 공유기 설치

아이디어

거리의 최댓값을 구하는 문제이므로 start, end값도 거리값으로 지정해주었다.
start = 1
end = 가능한 최댓값 (맨 끝집 사이의 거리)

나머지 과정은 이분탐색 패턴과 동일하다.
이 문제에서 새로웠던 점은 가장 인접한 공유기 사이의 거리의 최댓값을 구해야 하기 때문에 최댓값을 발견하면 기존 값(check(공유기 수), home_check(현재 기준 가장 인접한 최댓값을 만드는 공유기의 위치))들을 업데이트 해주었다.

코드

# 공유기 설치
import sys
N,C = list(map(int,sys.stdin.readline().split()))
home = [int(sys.stdin.readline().rstrip()) for x in range(N)]
home.sort()

# 거리의 최댓값을 구하는 문제 -> start,end도 거리값으로 지정
start = 1 # 거리 최소
end = home[-1] - home[0] # 거리 최대

result = 0
while(start <= end):
    check = 1
    mid = (start + end) // 2
    home_check = home[0]
    for h in home:
        if h - home_check >= mid:
            check += 1
            home_check = h
    if check < C:
        end = mid - 1
    else:
        start = mid + 1
        result = mid
print(result)