백준 #2212 센서

코드

import sys
# sys.stdin = open("input.txt")
input = sys.stdin.readline


n = int(input()) # 센서 개수
k = int(input()) # 집중국 개수
arr = list(map(int, input().rstrip().split()))
arr.sort()

dist = []
for i in range(n - 1):
	dist.append(arr[i + 1] - arr[i])

dist.sort(reverse=True)
print(sum(dist[k - 1:]))

풀이

먼저 센서들의 좌표를 정렬해준다음 인접한 센서들의 거리를 구해주었다.

거리들을 저장한 배열을 내림차순 정렬해준 뒤에 k -1 번 인덱스부터 합을 구해준다!

이유는 k개의 집중국을 만들려면 k - 1번 센서들을 나누어 주어야하는데 인접한 거리가 가장 긴 애들을 떼어내주면 되기때문이다.