문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

예제 입력 1

5 3
1 3 5 6 10

예제 출력 1

3

센서(2212) 문제를 풀다가 내가 0개국어인건지 도저히 문제 자체가 이해가 안가서 질문 게시판을 참고했다. 그래서 겨우 무슨 문제인지 이해를 했는데 행복 유치원과 풀이 방법이 같다고 해서 이 문제를 풀어보았다.

오름차순으로 정렬된 숫자들을 k개의 조로 나누되, 한 조의 조원들은 모두 인접해 있어야 하고, 한 조에서 가장 키가 큰 친구 - 가장 키가 작은 친구의 차이를 최소화 해야 한다? 이를 그림으로 표현하면 아래와 같다.

노란 글씨는 앞사람과의 간격이고, 빨간줄은 조를 나눈 것이다.
앞사람과의 간격이 클수록, 한 조 내에서 원생 간의 거리의 합산에서 포함될 일이 없도록 만들어야 한다.
그래서 간격을 오름차순 정렬해서 큰 수 부터 제거해야 한다. 그런데 k개의 조로 나누는 것이기 때문에 k - 1번 제거하면 된다.

그래서 나의 코드는

나의 코드

from sys import stdin as s

# s = open("input.txt", "rt")  # 주석 처리해야 하는 부분

n, k = map(int, s.readline().split())
heights = list(map(int, s.readline().split()))

interval = []
for i in range(1, n):
    interval.append(heights[i] - heights[i - 1])
# 앞 사람과의 차이가 들어있는 리스트를 오름차순 정렬
interval.sort()

# k개의 조로 나누므로 간격이 큰 숫자부터 k - 1번 pop한다.
for _ in range(k - 1):
    interval.pop()

print(sum(interval))