백준 2110 : 공유기 설치 [파이썬]

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

2110번: 공유기 설치

1. 문제 설명

1	2	4	8	9
o		o		o

이런식으로 최대한 공유기를 떨어뜨려서 설치한 후에

그중에 가장 가까운 공유기 사이의 거리를 구하는 문제이다.

 

2. 코드설명

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
home = [int(input()) for _ in range(n)]
home.sort()

start  = 1
end = home[n-1] - home[0]
res = 0

while start<=end:
    mid = (start+end)//2
    current = home[0]
    count = 1

    for i in range(1, n):
        if home[i] >= current + mid:
            count += 1
            current = home[i]
    
    if count >= c:
        start = mid + 1
        answer = mid
    else:
        end = mid - 1

print(answer)

• home 리스트에 딥들이 좌표를 입력받은 후에 정렬
• start = 1, end = home[n-1] - home[0] 으로 설정(시작은 최소 거리, 끝 값은 최대 거리)
• 앞 부터 공유 설치
• 설치할 수 있는 공유기 개수가 가지고 있는 공유기 개수보다 많다면 그 뒤에도 설치 할 수 있으므로 설치 거리 mid를 +1하여 다시 앞부터 설치
• 반대라면 좁게 설치해야 하므로 mid - 1로 설정하여
• 답 구하기