백준 2110번 <공유기 설치>

백준 알고리즘 2110번

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

2110번: 공유기 설치

2110번

N개의 집에 C개의 공유기를 적당히 설치해서 가장 인접한 두 공유기 사이의 거리를 최대로 하여라.

 

입력으로 첫 줄에 집의 개수 N과 공유기의 개수 C가 들어온다. 다음 줄부터 N개의 집의 좌표가 주어진다.

 

출력으로는 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

문제 해결

이진 탐색을 이용하여 문제를 해결하였다.

집의 좌표 X가 최대 1,000,000,000이고 집의 개수 N이 최대 200,000로 범위가 매우 크다.

따라서 이진 탐색을 이용하여 O(N * log X)로 문제를 해결해야 한다. 20만 * log(10억)으로 20만 * 30

 

재귀함수가 아니라 반복문을 이용하여 이진 탐색을 구현하였다.

이때 이진 탐색에서 사용할 start는 집 간 최소 거리가 될 수 있는 1로 하였고 end는 가장 처음에 있는 집과 가장 마지막에 있는 집의 거리의 차로 하였다.

 

import sys
input = sys.stdin.readline

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

homes = []
for _ in range(n):
    temp = int(input().rstrip())
    homes.append(temp)
homes = sorted(homes)
start = 1
end = homes[n-1] - homes[0]
result = 0
while start <= end:
    mid = (start + end) // 2
    count = 1
    value = homes[0]
    for i in range(1, n):
        if homes[i]-value >= mid:
            value = homes[i]
            count += 1
    if count >= m:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

start가 end보다 커지면 while문을 빠져나올 수 있도록 하였다.

또한 설치한 공유기를 의미하는 count와 인접한 공유기를 의미하는 value를 이용하였다.

첫번째로 있는 집에는 공유기를 무조건 설치해야하므로 count를 1로 value는 homes[0]으로 초기화하였다.

for문을 돌려서 두 번째 집부터 시작하여 인접한 공유기와의 거리가 mid보다 크거나 같으면 공유기를 설치했다. 즉 count에 1을 더하고 value를 homes의 해당 인덱스 값으로 설정했다.

for문이 끝나고 count가 만약에 m과 같거나 크다면 start를 mid + 1로 설정하고 (더 큰 거리를 갖는 경우가 있을 수 있기 때문에) mid를 result에 저장해두었다. count가 m보다 작다면 거리를 좁혀야 하기 때문에 end를 mid -1로 설정하였다.