[BOJ] #2110 - 공유기 설치

2110번: 공유기 설치

 

 

** 문제 유형

• 이진 탐색

 

** 풀이

1. 집의 개수 N은 최대 200,0000이면, 집의 좌표 X는 최대 1,000,000,000
2. 이진 탐색을 이용하여 O(N*logX) 안에 문제 해결
   • 200,000 * 30 ≒ 6,000,000
3.  가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾음
   • 반복적으로 Gap을 설정하며, C개 이상의 공유기를 설치할 수 있는 경우를 찾음
     • 최대 Gap = max / 최소 Gap = min
     • mid = (max + min) // 2
   • mid 만큼의 거리를 두고 공유기를 설치한다고 가정했을 때, 설치 가능한 공유기의 개수를 확인하여 C와 비교
     
     • C보다 작을 경우, Gap(= mid)을 감소시킴 -> max = mid - 1
     • C 이상일 경우, 현재의 Gap을 저장하고 Gap을 증가시킴 -> min = mid + 1
   • max와 min이 같아지면, 더 이상 Gap을 증가시킬 수 없으므로 최적의 경우임

 

n, c = map(int, input().split())

houses = []
for _ in range(n):
    houses.append(int(input()))
houses.sort()

start = 1 # 좌표 값의 최소 값
end = houses[-1] - houses[0] # 가장 높은 좌표와 가장 낮은 좌표의 차이
rslt = 0

while start <= end:
    mid = (start + end) // 2 # mid는 Gap을 의미
    value = houses[0]
    count = 1
    
    for i in range(1, len(houses)):
        if houses[i] >= value + mid:
            value = houses[i]
            count += 1
        
    if count >= c: # C개 이상의 공유기 설치 가능
        start = mid + 1
        rslt = mid # 최적의 경우 저장
    else: # C개 이상의 공유기 설치 불가 -> Gap이 너무 큼
        end = mid - 1

print(rslt)