❓2110번 : 공유기 설치
〽️ 문제 요약
집 N개가 있을 때 공유기를 C개 설치하려고 하는 경우 가장 가까운 두 공유기 사이의 거리를 최대로 하는 경우 최대 거리를 구하면 되는 문제
🤨 접근법
가까운 두 공유기 사이의 거리가 H일 때 공유기를 C개 이상 놓을 수 있는가에 대한 결정 문제를 통해 공유기를 C개 이상 놓을 수 있는 가장 가까운 두 공유기 사이의 최대 거리를 구하는 최적화 문제를 해결해야 한다 (파라메트릭 서치).
결정 문제의 로직은 가장 가까운 두 공유기 사이의 거리를 H로 두었을 때 C개 이상 놓을 수 있는지를 검사한다. 집의 좌표가 오름차순으로 주어지지 않으므로, 좌표를 모두 받은 후 정렬을 수행해 주었다.
그리고 첫번째 집에 공유기를 두고, 다음 집의 좌표가 H 이내에 있으면 두 공유기 사이의 거리가 H보다 작은 것이 되어버리므로 생략하고, H보다 멀리 있는 집을 찾으면 공유기를 설치(카운트) 후 다음 반복때 해당 집과 또 다시 H 떨어져 있는 다음 집을 찾는다. 전체 집의 좌표를 순회했을 때 공유기가 C개 이상 설치된다면 해당 결정 문제를 만족한다. 즉, 두 공유기 사이의 거리가 최대 H일 때 공유기를 C개 놓을 수 있다.
이제 C개를 놓을 수 있는 두 공유기 사이의 최대 거리를 구하는 최적화 문제를 해결해야 한다. 최대 거리를 H라고 했을 때 H보다 작은 거리에 대해서는 모두 결정 문제를 만족하고, H 보다 큰 거리에 대해서는 모두 결정 문제를 만족하지 못할 것이다.
이러한 H를 순차 탐색으로 찾기에는 집 좌표 범위가 최대 1,000,000,000까지 주어지므로 시간 초과가 발생한다. 이분 탐색으로 찾아보자.
공유기를 놓을 수 있는 두 집 사이의 거리의 최소는 1 최대는 정렬된 집 좌표의 첫 좌표와 마지막 좌표의 차이 만큼이다. 그 중간부터 결정 문제를 만족하는지 검사한다.
결정 문제를 만족한다면 최대 거리를 더 늘려서 다시 시도해볼필요가 있다. low = mid+1로 놓고 결정 문제를 반복한다. 결정 문제를 만족하지 못한다면 최대 거리를 좁혀서 다시 시도해본다. high = mid-1로 놓고 결정 문제를 반복한다. low가 high를 역전하여 반복이 종료된 경우 high에는 공유기를 C개 이상 놓을 수 있는 가장 가까운 두 공유기 사이의 최대 거리. 즉, 답이 담겨 있다.(참고)
🔡 코드
import sys
input = sys.stdin.readline
N, C = map(int, input().rstrip().split())
houses = sorted([int(input()) for _ in range(N)])
def can_set_more(term):
before = houses[0]
count = 1
for i in range(1, N):
if houses[i]-before >= term:
count += 1
before = houses[i]
if count >= C:
return True
def setting(low, high):
while low <= high:
mid = (low+high)//2
if can_set_more(mid):
low = mid+1
else:
high = mid-1
return high
print(setting(1, houses[-1]-houses[0]))