백준 13164. 행복 유치원

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

13164번: 행복 유치원

 

코드

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

sub = []
for i in range(1, n):
    sub.append(p[i]-p[i-1])

sub.sort()
for _ in range(k-1):
    sub.pop()
print(sum(sub))

 

N명의 원생을

각 조에는 적어도 한 명이 존재하게, 조 별로 인원수가 같은 필요는 없게

K개의 조로 나누고,

조마다 티셔츠 만드는 비용은 (가장 키 큰 원생) - (가장 키 작은 원생) 일 때

전체 비용의 최솟값을 구하는 문제였다.

 

전체 비용이 최솟값이 되기 위해서는

각각의 편성된 조에서 (가장 키 큰 원생) - (가장 키 작은 원생)가 최소가 되어야 함으로

정렬된 원생들 사이의 키 차이 값을 구해서

키 차이가 큰 구간을 조를 나누는 지점으로 선택하면 되겠다고 생각했다.

 

K개의 조로 나누기 위해서는 조를 나누는 지점은 K-1개 선택되어야 한다.