[이진 탐색] 공유기 설치 (BAEKJOON - 2110)

1. 문제

N개 집의 위치가 배열로 주어졌을 때, 공유기를 C개만큼 설치할 경우, 공유기 사이의 거리가 최대를 출력

 

2. 입력

# SET - 1
5 3
1
2
8
4
9

 

3. 출력

# SET - 1
3

 

4. 풀이

떡볶이 떡을 자르는 문제처럼 공유기 사이의 거리를 이진탐색으로 찾아서 푸는 문제

 

공유기 사이의 거리가 최소거리 1부터 배열의 N-1번째에서 0번째를 뺀 값이 최대거리일 때,

그 값의 가운데를 최소거리로 잡고 1번째부터 하나씩 공유기를 설치해나감 (0번째는 이미 설치했다고 가정)

설치한 공유기의 수가 C를 만족시키면 GAP을 늘리고 (binary search 오른쪽부분)

공유기의 개수가 딸리면 GAP을 줄임 (binary search 왼쪽 부분)

 

5. 코드

import sys
wr = sys.stdin.readline
N, C = map(int, wr().split())
houses = []
for _ in range(N):
    houses.append(int(wr()))

houses.sort()

start = 1
end = houses[-1] - houses[0]
result = 0

while start <= end:
    mid = (start+end) // 2
    value = houses[0]
    count = 1
    for i in range(1, N):
        if houses[i] >= value+mid:
            value = houses[i]
            count+=1
    if count >= C:
        start = mid+1
        result = mid
    else:
        end = mid-1
print(result)