2110_공유기 설치

문제는 더보기!

 

공유기 설치

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

128 MB

35200

12390

8924

38.684%

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

5 3
1
2
8
4
9

예제 출력 1 복사

3

 

 

문제의 접근을 처음에는 거리를 어떻게 나누지? 라 생각하다가 생각을 고쳤더니 쉽게 해결되었다

 

공유기간의 거리는 결국 0 ~ 100000000 안에서 결정되게 된다.

 

이 값들 사이에서 이분탐색을 통해서 값을 찾아나가면 된다.

 

즉 거리가 3이라면 각 집간 거리가 3은 이상이지만 가장 가까운 집들을 뽑아서 개수를 세주면 된다.

 

그렇게 구한 집의 개수가 공유기의 개수보다 많다면 더 큰거리를 두어도 괜찮다는 의미이므로 범위를 줄여줄 수 있다.

 

import sys
n,c = map(int,sys.stdin.readline().split())
lst = [ int(sys.stdin.readline()) for _ in range(n) ]

lst.sort()
start,end = 0,100000000

while start <= end:
    mid = (start + end) //2
    cnt = 1
    tmp = [lst[0]]
    for i in lst:
        if i-tmp[-1] > mid:
            cnt +=1
            tmp.append(i)
    if cnt >= c:
        start = mid +1
    else :
        end = mid -1
print(max(start,end))