[백준] 2110 공유기 설치

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

내 풀이

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
house = [int(input()) for _ in range(n)]
house.sort()

def is_possible(distance):
    count = 1  # 첫 번째 집에 설치
    last_location = house[0]
    for i in range(1, n):
        if house[i] - last_location >= distance:
            count += 1
            last_location = house[i]
    return count 

left = 1
right = house[-1] - house[0]
answer = 0
while left <= right:
    mid = (left + right)//2
    if is_possible(mid) >= c:
        answer = mid
        left = mid + 1
    else:
        right = mid - 1
    
print(answer)

시간 복잡도 → $O(N\, log\, D)$
$D$ 는 right를 의미 (공유기 사이의 최대 거리)
이분 탐색을 진행하며 $O(log \,D)$ 의 시간 복잡도가 소요되고, is_possible 에서 house를 순회하며 연산하므로 $O(N)$ 의 시간 복잡도 소요
공간 복잡도 → $O(N)$
$\because$ house 리스트 사용

코멘트

이 문제는 이분 탐색을 활용하여 인접한 두 공유기 사이의 최대 거리를 찾는 문제이다. 처음에는 모든 공유기 사이의 거리가 모두 같지 않고, 인접한 집과 떨어져 있는 집을 어떻게 고려하여 공유기를 배치해야할지 모르겠어서 헤맸는데 그리디를 함께 활용하여 해결할 수 있었다.

우선 공유기 사이의 최소 거리를 탐색하며, 이 거리일 때 총 몇 개의 공유기를 설치할 수 있는지 확인하는 is_possible 함수를 이용한다. 이 함수에서 반환한 설치 공유기의 갯수가 실제 공유기 갯수보다 많다면 공유기 사이의 거리가 너무 작다는 의미이므로 left = mid + 1을 해준다. 다만 우리가 구하고자 하는 것은 인접한 두 공유기 사이의 "최대" 거리를 구하는 것이므로 이 때 answer = mid 로 답을 업데이트 해준다. 함수에서 반환한 설치 공유기의 갯수가 실제 공유기의 갯수보다 적다면 거리가 너무 넓다는 것이므로 right = mid - 1를 하여 간격을 줄여준다.

[백준] 2110 공유기 설치

문제

입력

출력

내 풀이

코멘트

References