boj 2212 센서(골드5)

문제

https://www.acmicpc.net/problem/2212

집중국의 개수 k개만큼 덩어리를 나눌 수 있으므로

만약 집중국이 없었다면 모든 선을 이어야 하겠지만
집중국이 생기므로 인해 (k-1)개 만큼은 선을 없애도 된다.

ex) k=2일경우 크게 두 덩어리로 나눌 수 있으므로 모든 연결선 중에 1개는 뺴도 된다.
따라서 선 간의 거리를 다 재놓고 가장 큰거부터 k-1개 삭제해준 후 남아있는 선들 다 합치면 되는 문제이다!

풀이

import sys
input = sys.stdin.readline

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

arr = list(map(int,input().split()))

arr.sort()

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

distance.sort()

if k >=n:
  print(0)
  sys.exit()

if k != 1 :
  for _ in range(k-1):
    distance.pop()

print(sum(distance))

결과