문제

BOJ 2110: 공유기 설치 https://www.acmicpc.net/problem/2110

풀이

조건

• 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
• 집의 개수 : 최대 1,000,000,000개

풀이 순서

• 공유기의 거리를 이진 탐색을 통해 찾는다.
• 설정한 공유기의 거리를 통해 공유기를 몇 대 설치할 수 있는지 확인한다.
• 구한 공유기 대수가 목표보다 크다면 공유기 사이의 거리를 늘린다.
• 구한 공유기 대수가 목표보다 작다면 공유기 사이의 거리를 줄인다.

코드

Python

N, C = map(int, input().split())

arr = []
for _ in range(N):
    arr.append(int(input()))
arr.sort()

start = 1 # 공유기 거리 최소
end = arr[-1] - arr[0] # 공유기 거리 최대
result = 0

# 재귀로 적절한 두 공유기 사이의 거리를 찾는다
while (start <= end):
    mid = (start + end) // 2 # 현재 공유기 거리
    current = arr[0]
    count = 1

    # 공유기 설치 몇 대 할 수 있는지 체크
    for i in range(1, len(arr)):
        if arr[i] >= current + mid:
            count += 1
            current = arr[i]
    # 공유기 설치 수가 목표 보다 크면 공유기 사이 거리 늘림
    if count >= C:
        start = mid + 1
        result = mid
    # 공유기 설치 수가 목표 보다 작으면 공유기 사이 거리 줄임
    else:
        end = mid - 1

print(result)

정리

• 공유기 사이의 거리를 이진 탐색을 통해 구한다는 점을 떠올리기 어려웠다.