[Python] 백준 #2212 센서(탐욕 알고리즘)

이번 문제는 문제의 뜻을 해석하느라고 아주 어려웠네요.

 

censors on highway

 

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

2212번: 센서

 

문제는 수직선상에 있는 N개의 점들을 K개의 그룹으로 나누었을 때, 각각의 그룹의 길이의 합을 최소로 하는 문제입니다.

가장 쉬운 것은 두점사이의 거리가 가장 먼 것들에 대해서 K-1개 선택해서 나누면 됩니다.

 

문제의 예제처럼 1 6 9 3 6 7 위치들의 점이 있다고 한다면, 이것을 순서대로 정렬하면, 1 3 6 6 7 9 가 됩니다.  이 점들을 두개의 그룹으로 나눈다면, 가장 거리가 멀리 떨어져 있는 3 6을 선택해서 (1 3) (6 6 7 9)로 나누면 됩니다.  그러기 위해서는 두번째 점부터 이전점까지의 거리를 계산하고 그것을 정렬한 다음 K-1개만큼 가장 큰 값을 제거후 합을 구하면 됩니다.

 

제가 작성한 소스입니다.

"""
//    baekjoon #2212
//        - by Aubrey Choi
//        - created at 2023-07-19
"""
import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
v = list(map(int, input().split()))
v.sort()
d = [ v[i]-v[i-1] for i in range(1, n) ]
d.sort()
print(sum(d[:len(d)-k+1]))