[백준] 2212번 - 센서 (파이썬)

bled 2021. 5. 15. 20:44

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

2212번: 센서

첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며

www.acmicpc.net

[코드]

import sys
import heapq
sensor_num = int(sys.stdin.readline())
K = int(sys.stdin.readline())
sensors = list(map(int, sys.stdin.readline().split()))
sensors.sort()
distance = [abs(sensors[i] - sensors[i+1]) for i in range(len(sensors)-1)]
heap = []
[heapq.heappush(heap, (-x, x)) for x in distance]
if K-1 <= len(heap):
    [heapq.heappop(heap) for _ in range(K-1)]
    sum = 0
    for v in heap:
        sum += v[1]
    print(sum)
else:
    print(0)

일직선상에 N개 점이 있고 이들을 다 포함하는 K개의 선분들을 만들어야 할 때 선분 길이의 합이 최소여야 하는 문제