1. 문제 설명

센서

2. 문제 분석

수신 가능한 영역이 최솟값이어야 그 합이 최소가 된다. 수신 가능한 영역은 곧 각 센서 위치의 차의 합으로 계산할 수 있다. 수신의 개수는 n-k개로, 집중국 k개만큼 커버할 수 있기 때문에 전체 n개 중 k개를 뺀 수만큼만 계산한다.

3. 나의 풀이

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())
sensors = list(map(int, sys.stdin.readline().rstrip().split()))
sensors.sort()
pq = []
for cur, next in zip(sensors[:-1], sensors[1:]):
    distance = next - cur
    heapq.heappush(pq, [distance, cur, next])
total = 0
for _ in range(n-k):
    distance, cur, next = heapq.heappop(pq)
    total += distance
print(total)