[백준 2110] 공유기 설치

문제 

N개의 집이 수직선 위에 놓여있다. 여기서 C개의 공유기를 설치하려고 한다.

한 집에 공유기를 하나만 설치하여 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하려면 얼만큼의 거리로 C개의 공유기를 놓아야하는지 구하라

 

입력

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

 

출력

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

---

접근

이분탐색으로 접근을 하였다.

공유기를 설치한 집의 거리를 D라고 할 때 C개를 설치한 집들간의 거리가 D이상이 되어야한다.

예를 들어 1 2 4 8 9에 집이 있고 3개를 설치한다고 하자.

 

1 2 4에 이렇게 3개를 설치하면 D는 1이된다. 

D가 2라면 1다음에 2에 설치하지 못한다.

D가 2라면 2 4 8 이렇게 설치할 수 있을 것이다.

 

이렇게해서 최대거리인 D를 구해야한다. 이를 이분탐색으로 찾아보자

 

구현

집과 설치해야할 공유기의 개수를 입력받고 집의 좌표를 houses에 저장한다

그리고 이분탐색을 위해 houses를 오름차순으로 정렬한다.

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

 

그리고 탐색의 범위를 정한다.

left=1부터 right는 제일 멀리있는 집의 좌표를 넣어준다.

left = 1
right = houses[-1]

 

이분탐색을 진행하고 left와 right를 통해 mid를 구한다.

mid거리만큼 공유기를 C개 설치할 수 있는지 확인한다.

현재 집에서 mid만큼 더하여 다음 집의 범위 안에있다면 count를 증가시킨다.

 

그다음 count와 C를 비교하여 C보다 크다면 작은 쪽(left)의 범위를 좁히고 작다면 큰 쪽(right)의 범위를 좁힌다.

여기서 if문을 통해 answer를 계속 갱신하여 최댓값을 찾는다.

while left <= right:
    mid = (left+right)//2
    count = 1
    cur_pos = houses[0]
    for i in range(1, N):
        if cur_pos + mid <= houses[i]:
            count += 1
            cur_pos = houses[i]

    if count >= C:
        left = mid + 1
        answer = mid
    else:
        right = mid - 1

 

---

전체 코드

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

left = 1
right = houses[-1]
while left <= right:
    mid = (left+right)//2
    count = 1
    cur_pos = houses[0]
    for i in range(1, N):
        if cur_pos + mid <= houses[i]:
            count += 1
            cur_pos = houses[i]

    if count >= C:
        left = mid + 1
        answer = mid
    else:
        right = mid - 1
print(answer)