Q29. 공유기 설치

띠리링구 2022. 4. 10. 17:22

2110번: 공유기 설치

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

www.acmicpc.net

이건 솔직히 말해서 문제 이해를 제대로 못해서 그냥 답지를 봤다.

문제 풀이 전체의 시간복잡도는 N log N으로 풀어야되고

인접한 공유기 사이의 최소 거리를 변수로 두고 이진탐색으로 조절해가면서(log N)

공유기를 쫙 설치해보고 개수를 세봐야한다. (N)

그 개수가 C개 이상인지 미만인지를 보고 인접공유기 최소거리를 조절해가면 된다.

문제가 명확하지 않아서 썩 맘에 들진 않네

n,c = map(int,input().split())

array = []
for _ in range(n):
    array.append(int(input()))
array.sort()

start = 1
end = array[-1] - array[0]
result = 0

while start <= end:
    mid = (start + end) // 2
    value = array[0]
    count = 1
    for i in range(1,n):
        if array[i] >= value + mid:
            value = array[i]
            count += 1

    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid -1

print(result)