[백준] 2212 센서 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/2212
• 🔑 그리디, 정렬
  • n = 6  (센서 개수)
  • k = 2    (집중국 개수)
  • 1 6 9 3 6 7 (센서 위치)
  • 입력받은 센서들의 위치를 오름차순 정렬한다.
    • [1, 3, 6, 6, 7, 9]
  • 이 센서들의 간격을 구하고 오름차순 정렬한다.
    • [0, 1, 2, 2, 3]
  • 집중국이 2개니까 센서들의 위치를 2등분을 해야 한다.
  • 이 나누는 기준을 간격이 가장 큰 위치로 한다.
  • 결론적으로 간격이 긴 k-1개를 제외하고 합한다.

 

n = int(input())
k = int(input())

sensor = list(map(int, input().split()))
sensor.sort()

sensor_distance = []
for i in range(1, n):
    sensor_distance.append(sensor[i] - sensor[i-1])
sensor_distance.sort()

answer = sum(sensor_distance[:n-k])

print(answer)