난이도: 2 / 풀이 시간: 50분 / 시간 제한: 2초
link: https://www.acmicpc.net/problem/2110
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력 조건
출력 조건
가장 인접한 두 공유기 사이의 최대 거리
를 출력합니다.힌트
입력 예시
5 3 1 2 8 4 9
출력 예시
3
풀이 특징
설치된 공유기 위치와 현재 확인중인 위치까지의 거리가 중앙 Gap 보다 크거나 같은 경우 -> 해당위치 공유기 설치
# 가장 인접한 두 공유기 사이의 거리(gap)의 최댓값
import sys
input = sys.stdin.readline
# 집수, 공유기수
n, c = map(int, input().split())
locations = [int(input()) for _ in range(n)]
locations.sort()
# 파라메트릭 서치: `가장 인접한 두 공유기 사이의 거리(gap)` 값을 조절
# 공유기수가 c와 같다면 -> gap을 높인다 (마지막 gap 값 저장)
# 공유기수가 c보다 많다면 -> gap 을 높인다
# 공유기수가 c보다 적다면 -> gap 을 낮춘다
# 공유기수를 어떻게 계산? -> 설치된 공유기위치 + 현재 gap 보다 크거나 같은 위치의 경우: 공유기 설치 가능위치
def parametricSearch(locations, c, minGap, maxGap):
# 마지막에 저장된 Gap 값
lastGap = 0
while minGap <= maxGap:
# 최소 Gap ~ 최대 Gap 에서 중앙 Gap 값으로 파라메트릭 서치 진행
mid = (minGap + maxGap) // 2
# 설치된 공유기 수 (초기값 1: [0])
count = 1
# 설치된 공유기 위치값
baseValue = locations[0]
# 공유기 설치 진행
for i in range(1, n):
if locations[i] >= baseValue + mid:
baseValue = locations[i]
count += 1
# 설치된 공유기수가 c 보다 크거나 같은 경우 -> Gap 을 높인다
if count >= c:
lastGap = mid
minGap = mid + 1
else:
maxGap = mid - 1
# 마지막 Gap값 반환
return lastGap
minGap = 1
maxGap = locations[n-1] - locations[0]
print(parametricSearch(locations, c, minGap, maxGap))