[백준/그리디] 2212번 센서

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

2212번: 센서

 

목표 : n개의 센서들을 k개의 구간으로 나눕니다.

 

0. 집중국의 개수가 더 많으면, 센서마다 집중국을 설치하면 되므로 0 입니다.

1. 오름차순으로 센서 위치를 정렬합니다.

2. 센서 사이의 거리를 구하고, 내림차순으로 정렬합니다.

3. 거리 합이 최소인 k구간으로 나누기 위해,거리로 정렬한 것에서 k-1번째의 거리들을 사용합니다. 

 

import sys

input = sys.stdin.readline

n = int(input())
k = int(input())
sensorPoint = sorted(list(map(int,input().split())))

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

dist = []
for i in range(1,n):
    dist.append(sensorPoint[i] - sensorPoint[i-1])
dist.sort(reverse=True)
print(sum(dist[k-1:]))