📚 2212 - 센서

센서

이해

문제를 이해하기 힘들어 예시를 참고했다.

참고

6
2
1 6 9 3 6 7

5

-> 집중국 두개가 각각 [1, 3] [6, 9] 영역을 커버하면 최소 길이가 됩니다.


10
5
20 3 14 6 7 8 18 10 12 15

7

-> [3, 3], [6, 8], [10, 15], [18, 18], [20, 20] 로 분할하면 최소 길이가 됩니다.

집중국을 센서의 좌표에 두고 길이를 재면 된다.

10
5
20 3 14 6 7 8 18 10 12 15

7

-> [3, 3], [6, 8], [10, 15], [18, 18], [20, 20] 로 분할

이 되는데, 3 6 7 8 10 12 14 15 18 20로 정렬 후, 사이의 거리를 계산한 후 최소끼리 k개 합한 것이 나누고자 하는 영역과 같다.

위 예시를 보면 10 12 14 15의 간격은 5인데, 이는 2 + 2 + 1와 같다.
두 사이의 거리 내림차순으로 정렬한 후 k-1 인덱스부터 n-1인덱스까지 꺼내면 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값이 된다.

소스

import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
k = int(read())  
  
sensor = list(map(int, read().split()))  
s = []  
  
sensor.sort()  
  
for i in range(1, n):  
    s.append(abs(sensor[i] - sensor[i-1]))  
  
s.sort(reverse=True)  
answer = 0  
  
for i in range(k-1, n-1):  
    answer += s[i]  
print(answer)