Point 💡

• 문제 자체를 이해하는데 어려웠고, 어떻게 잘라야하는지 해결책을 찾지못했다.

20 3 14 6 7 8 18 10 12 15
# 3 6 7 8 10 12 14 15 18 20 
# 3, 1, 1, 2, 2, 2, 1, 3, 2
# 1, 1, 1, 2, 2, 2, 2, 3, 3

이런 예제가 주어졌을 경우, 센서사이의 거리가 최소가 되어야하기 때문에 3 6 7 8 10 12 14 15 18 20으로 정렬시켰다.

K개의 집중국의 수신 가능영역을 [3, 3], [6, 8], [10, 15], [18, 18], [20, 20]로 분할하면 최소 길이가 된다.

센서 사이의 거리를 하나씩 파악해서 리스트에 저장한다.

센서 사이의 거리가 가장 큰 부분을 삭제하면 분할한 것이므로 집중국을 하나 설치한 것이 된다.

거리 리스트를 오름차순으로 정렬하여 맨 뒤에서 집중국의 개수만큼 큰 숫자를 하나씩 삭제한다.

My Solution

import sys

# 행복한 유치원 문제와 비슷

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
sensor = list(map(int, sys.stdin.readline().split()))
sensor.sort()

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

distance.sort()
print(sum(distance[:n-m]))