[Python] 백준 13164. 행복 유치원

 

문제 링크

 

 

풀이

인접한 아이들의 키 차이를 구하고 내림차순 정렬해서 상위 k-1명을 제외한 후 나머지의 차이의 합을 구하면 된다.

 

코드

'''
인접한 것들 중 차이가 큰 친구들을 나눠서 4조를 만들어보자
1, 50 | 500 | 5000 | 5500, 5600
(49,1) (450,2) (4500,3) (500,4) (100,5)
선택된 것들은 3,4,2인데
총 비용은 3,4,2의 차이를 제외한 1과 5의 합 149

1, 50 | 500 | 5000, 5001 | 6000, 6001, 6002
(49,1) (450,2) (4500,3) (1,4) (999,5) (1,6) (1,7)
3과 5와 2가 선택됐고
49+1+2
결국 선택된 2,3,5를 제외하면 된다
differ 순으로 내림차순, k-1개 만큼 선택, 나머지의 합
'''
import sys
input = sys.stdin.readline
n, k = map(int, input().split())
ls = list(map(int, input().split()))
differ_ls = []
for i in range(n-1):
    differ = ls[i+1] - ls[i]
    differ_ls.append(differ)
differ_ls.sort(reverse=True)
print(sum(differ_ls[k-1:]))