Comment
센서들의 위치는 고속도로 위에서 그려보면 원점을 기준으로 위치가 멀 수록(숫자가 클 수록) 점점 오른쪽에 순서대로 배치될 것이다. 나는 인접한 센서들 간의 거리의 차를 구할 것이기 때문에 우선 센서들의 위치를 오름차순 정렬해줬다.그리고나서, 인접한 센서들 사이의 거리를 계산해서 array 배열에 저장해준 뒤 각 거리들의 차를 오름차순 정렬해준다.
만약 센서(n)의 갯수가 6개고, 집중국(k)의 갯수가 2개라고 한다면 집중국의 수신 가능 영역의 길이의 합의 최솟값은 n-k=4개의 거리들의 차를 앞에서부터 차례로 더해준 값과 같다.
1 3 6 6 7 9 : 센서들의 위치
2 3 0 1 2 : 인접한 센서들 간의 거리 차이
3과 6의 거리 차가 가장 크므로 이 구간을 나눠서 (1, 3) (6, 6, 7, 9) 로 센서들이 나뉘어야 집중국의 수신 가능 영역의 길의 합이 최소가 될 것이다.
따라서 거리들의 차를 오름차순 정렬한 0 1 2 2 3 에서 n-k=4개를 앞에서부터 더해주면 0+1+2+2=5 가 된다. 이때, 맨 뒤의 3을 제외한 숫자들이 더해지는데, 즉, 앞에서부터 n-k개를 더해준다는 것은 센서 간의 거리의 차가 가장 큰 값을 k-1개 빼주는 것과 같다고 볼 수 있다.
Code
import sys
n = int(input())
k = int(input())
sensor = list(map(int,input().split()))
sensor.sort() # 인접한 센서 사이 거리 구하기 위해
between = []
for i in range(1,len(sensor)):
between.append(sensor[i]-sensor[i-1]) # 인접한 센서 사이의 거리
between.sort()
answer = sum(between[:n-k]) # k개의 집중국 필요하면 k-1개 사이가 필요
print(answer)