백준 2110 - 공유기 설치 - 2021/03/31

문제 설명

 

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

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

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

 

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

 

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

 

내 생각

 

이진 탐색을 공부하고 사이트에서 문제를 풀다가 처음에 이 문제를 봤을때는 풀지 못했다. 일반적인 이진 탐색과 조금 달라 문제에 접근하는데 어려움이 있었다. 이 문제는 문제에서 주어지는 좌표에서 이진 탐색을 하는게 아니라 집 사이의 거리를 이진 탐색해야 한다.

 

그림에서처럼 1 2 4 8 9의 좌표가 주어질 때, 좌표간의 최소 거리는 1과 2사이 1이고 최대 거리는 1과 9사이 8이다.

 

최소 거리를 start로, 최대 거리를 end로 두고 mid를 계산하면 4이다. 좌표에서 거리가 4씩 떨어진 개수가 한개밖에 없기 때문에 (4와 8사이 or 4와 9사이) end를 mid-1로 수정해야한다.

 

그럼 start=1, end=3, mid=2이다. 여기서 다시 좌표에서 거리가 2씩 떨어진 개수를 구하면 (1과 4사이 or 2와 4사이) 그리고 (4와 8사이 or 4와 9사이)로 총 두개이다.

 

문제에서 주어진 c가 3이기 때문에 세개를 설치할 수 있다.

 

문제에서는 최대 거리를 구하는게 목표기 때문에 start<=end일 때 까지 이진탐색을 해야 한다.

 

이진 탐색을 한 번 더 하면 start=3, end=3, mid=3이고 이 경우에도 조건에 충족한다.

 

그래서 최대 거리를 구하면 3

 

n,c=map(int,input().split())
arr=[]
for i in range(n):
    arr.append(int(input()))
    
arr.sort()
start=1
end=arr[-1]-arr[0]
result=0
while (start <= end):
    mid = (start + end) // 2
    value = arr[0]
    count = 1
    for i in range(1, len(arr)):
        if arr[i] >= value + mid:
            value = arr[i]
            count += 1
    if count >= c:
        start = mid + 1
        result=mid
    else:
        end=mid-1
        
print(result)

 

개인적으로 일반적인 이진탐색 문제에서 한번 더 생각해야하기 때문에 조금 어려웠던 문제