[ 알고리즘 ] 백준 2110번: 공유기 설치

이주 weekwith.me·2022년 8월 11일

목록 보기

58/73

블로그를 이전 중이라 완료되기 전까지는 벨로그에 작성할 계획입니다.
이후 모든 글은 https://weekwith.me 에 작성 예정이니 다른 글이 궁금하시다면 해당 링크를 통해 방문해주세요.

본 글은 [ 백준 ] 2110번: 공유기 설치를 풀고 작성한 글입니다.

문제

설명

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

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

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

입력

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

출력

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

풀이

접근법

거리를 기준으로 이진 탐색이 이뤄지는 부분까지는 생각했는데 집까지의 거리를 구해서 C개의 공유기를 설치하는 방법에 대한 접근법이 떠오르지 않아 다른 사람의 접근법을 참고했다.

시작값과 끝값은 1과 가장 거리가 먼 경우, 다시 말해 오름차순으로 정렬된 집에 대해 첫 집과 끝 집의 거리로 할당하면 된다.

이후 반복문을 수행하며 해당 거리의 중간값을 계속해서 구하며 집에 대해 내부적으로 반복문을 한번 더 수행해서 만약 중간값보다 집 사이의 거리가 길면 갯수를 늘리고 그렇지 않으면 늘리지 않는다.

이렇게 구한 갯수가 C보다 크거나 같은 경우 집 사이의 거리를 더 늘려도 되기 때문에 시작값을 중간값에 1을 더한 값으로 재할당하고 그렇지 않으면 집 사이의 거리를 더 줄여야 하기 때문에 끝값을 중간값에 1을 뺀 값으로 재할당한다.

추가적으로 입력값이 매우 크기 때문에 내부 sys 모듈 내에 있는 readline() 내장 함수를 사용해서 입력값을 받아야 시간 초과가 되지 않는다.

나의 풀이

접근법을 토대로 문제를 풀면 아래와 같다.

import sys


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

houses.sort()
answer = 0
start, end = 1, houses[-1] - houses[0]
while start <= end:
    count = 1
    middle = (start + end) // 2
    previous_idx = 0
    previous_distance = end
    for idx in range(1, len(houses)):
        distance = houses[idx] - houses[previous_idx]
        if distance >= middle:
            count += 1
            previous_idx = idx
            if distance < previous_distance:
                previous_distance = distance

    if count >= C:
        if answer < previous_distance:
            answer = previous_distance
        start = middle + 1

    else:
        end = middle - 1

print(answer)