[백준] 2110 공유기 문제

1  문제 설명

• 백준 문제
• 난이도 : 중
• 문제 유형 : 이진 탐색
• 입력 : 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
• 출력 : 가장 입접한 두 공유기 사이의 최대 거리

2  문제풀이 아이디어

• 이진 탐색을 이용하여 O(N * logX)로 해결한다. (X = 집의 좌표)
  • 20만 * log10억 = 약 600만
• 두 공유기 사이의 최대 간격을 이진 탐색으로 찾는다.
• 탐색 범위가 클 때는 logX를 요구한다고 가정한다.
• 이진 탐색 구현 방법 : 재귀적 or 반복적

3  이진 탐색

• 탐색 범위를 절반으로 쪼개면서 탐색하는 방법이다.
• 배열 내부의 데이터가 정렬되어 있어야 사용할 수 있다.
• 필요한 변수 : 시작점, 끝점, 중간점
• 찾으려는 값과 중간점을 반복적으로 비교한다.
• 한번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어드므로 시간복잡도 O(logN)이다.

 

n, c = list(map(int, input().split(' ')))
            
array = []
for _ in range(n):
    array.append(int(input()))
array = sorted(array)
            
start = array[1] - array[0] # 최소 거리
end = array[-1] - array[0] # 최대 거리
result = 0

while(start <= end):
    mid = (start + end) // 2 # 중간값 찾기
    value = array[0]
    count = 1
    for i in range(1, len(array)):
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid -1
            
print(result)