[BOJ] (G4) 2110. 공유기 설치

👨‍💻 개인 공부 기록용 블로그 입니다.
💡 틀린 내용이나 오타는 댓글, 메일로 제보해주시면 감사하겠습니다!! (__)

링크

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

문제

문제 설명 및 요점

• N 개의 집에 C개의 공유기를 설치한다.
• 각 공유기 간 간격 중 최솟값이 최대가 되는 거리를 찾는다.
• 각 집의 좌표는 1부터 10억까지의 범위로 주어진다.

풀이

#이진탐색 #매개변수탐색

• 탐색 범위가 괴랄함(10억) -> 이진탐색
• 최적화(최댓값 찾기) 문제를 결정 문제로 바꿔보자.
  • 가장 인접한 간격이 최대가 되는 거리 찾기
  • -> 특정 값(최대가 되는 거리)이 가장 인접한 간격이 될 수 있는가?
  • -> 특정 값으로 정답을 잡았을 때, 문제 조건을 모두 만족할 수 있는가?
• 이진탐색으로 탐색 범위를 좁혀가면서, mid 값이 문제 조건을 만족할 수 있는지 알아본다.
  • mid 간격 이상으로 공유기를 c개 이상 설치할 수 있는가?
  • 가능하다면, 일단 기록해놓고 탐색 범위를 해당 값 뒤로 좁혀본다.
  • 불가능하다면, 탐색 범위를 해당 값 앞으로 좁혀본다.

코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
routers = []
for _ in range(n):
    routers.append(int(input()))
routers.sort()


def check(dist):
    cnt = 1
    prev = routers[0]
    for router in routers[1:]:
        if router - prev >= dist:
            cnt += 1
            prev = router
    return True if cnt >= c else False


l, r = 0, 1_000_000_001
answer = 0
while l <= r:
    mid = (l + r) // 2
    if check(mid):
        answer = max(answer, mid)
        l = mid + 1
    else:
        r = mid - 1
print(answer)