[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 2110번 _ 공유기 설치

https://www.acmicpc.net/problem/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)가 한 줄에 하나씩 주어진다.

[출력]

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

 

[아이디어]

1) 크기 순으로 정렬했을 때, 0번째 집에는 무조건 설치한다.

2) 설치 가능한 최대 길이는 (최댓값 - 최솟값) 이다.

3) 1과 최대길이로 이분탐색을 실시하면서, 주어진 길이로 채울 수 있는만큼 공유기를 채운다.

4) 채운 공유기 수가 c보다 크거나 같은 경우와 작은 경우로 나누어 생각한다.

 

# Pypy3로 제출
n,c = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
lo = 1; hi = h[-1]-h[0]

while lo<=hi:
    mid = (lo+hi)//2
    cnt = 1
    for i,x in enumerate(h):
        if i ==0:
            a = x
        elif x-a >= mid:
            cnt+=1
            a = x
    # c개보다 많거나 같게 넣는 경우에는 간격을 더 줄여볼 여지가 있다.
    if cnt>=c:
        lo = mid + 1
    else:
        hi = mid - 1
print(hi)