[Python/파이썬] 백준 2110번 공유기 설치

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 = []
for _ in range(n):
    house.append(int(input()))

house.sort()

start, end = 1, house[-1] - house[0]
ans = 0
while start <= end:
    mid = (start + end) // 2
    now = house[0]
    num = 1
    
    for i in range(1, len(house)):
        if house[i] >= now + mid:
            now = house[i]
            num += 1
        
    if num >= c:
        ans = mid
        start = mid + 1
    else:
        end = mid - 1
        
print(ans)

처음에 Python3로는 시간 초과가 뜨길래 PyPy3로 제출해봤더니 맞았다. 그래서 

import sys
input = sys.stdin.readline

이거 추가해줬더니 Python3로도 통과됐다...

 

문제를 보고 뭔가 이분탐색을 써야할 거 같기는 한데 어떻게 해야할지 모르겠어서 한참 헤맸다.

답은 공유기를 설치할 최소 거리를 이분 탐색으로 찾으면 되는거였다.

1. 집의 위치를 house 배열에 입력받고 정렬해준다.
2. 공유기를 설치할 최소 거리를 찾기 위해 start와 end를 각각 1, house[-1] - house[0]로 설정하고 이분탐색을 해준다.
   1. mid = (start + end) // 2라 할 때, 집들을 순서대로 하나씩 살펴보며 현재 집에서 최소 거리를 더한 값(now + mid)보다 크거나 같다면 공유기를 설치할 집인 것이므로 현재 방문한 집을 now로 업데이트해주고 설치한 공유기 갯수값인 num을 1 증가시킨다.
   2. house 배열을 모두 살펴보고 난 뒤 num의 값이 설치하고자 하는 공유기 개수(c)보다 크거나 같다면 공유기를 더 멀리 설치할 수 있는 경우이므로 이 때의 mid 값을 ans에 저장해주고 start = mid + 1로 하여 거리를 더 넓게 설치할 수 있는지 살펴본다. 
   3. num의 값이 설치하고자 하는 공유기 개수(c)보다 작다면 너무 멀리 설치해서 원하는 공유기 갯수만큼 설치할 수 없는 경우이므로 end = mid - 1로 하여 탐색해준다.