[백준 2110] 공유기 설치

0. 제목

• 백준 2110 공유기 설치
• BOJ 2110 공유기 설치
• Python 2110 공유기 설치

---

1. 문제

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

---

2. 풀이

• 이진탐색을 사용하는 문제이다.
• 두 공유기 사이 거리의 최대값과 최소값을 가장 먼저 구하고 중간값을 구해가며 정답을 구한다.
• 중간값을 구할 때마다 설치 가능한 공유기 개수를 구한다.
• 설치 가능한 공유기 개수와 입력받은 공유기 개수를 비교해가며 범위를 조정한다.
• while문을 빠져나온 후 정답을 출력한다.

---

3. 코드

n, c = map(int, input().split(' '))
 
arr = []
for _ in range(n):
    arr.append(int(input()))
    
arr = sorted(arr)
 
low = arr[1] - arr[0]
high = arr[-1] - arr[0]
result = 0 # 결과값(최대 Gap)
 
while(low <= high):
    mid = (low + high) // 2 # mid는 gap
    
    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: # c개 이상의 공유기를 설치할 수 있는 경우
        low = mid + 1
        result = mid
    else: # c개 이상의 공유기를 설치할 수 없는 경우
        high = mid - 1
        
print(result)