https://www.acmicpc.net/problem/13164
시간 1초, 메모리 512MB

input :

• N K(1 ≤ N ≤ 300,000, 1 ≤ K ≤ N)
• N개의 숫자

output :

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

조건 :

• 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다.

모든 경우의 수를 따져야 하나 싶었는데 그렇다면 무엇을 기준으로 dp를 해야하는지를 모르겠었다.
그리고 보니 기준이 될 수 있는 수는 티셔츠 만드는 비용이기에 이분탐색을 하려 했다.

그런데 언제나 맨 앞에서 부터 모든 원생을 묶는 그룹이 생기지 않는 경우도 발생하기에 이 경우도 아니라고 보았다.

코드포스 문제중에 그룹을 나누는 문제가 있었다. 아마 임의의 숫자를 추가하면서 그룹을 나누는 것이였는데 그와 비슷한 방식으로 문제를 해결할 수 있다.

원생의 키 차이는 각 원소의 차의 절대값이다. 이를 통해서 알 수 있는 것은 무엇일까??

키 차이 == 모든 원소들의 키 차이

이를 알 수 있다.
예시
5 3
1 3 5 6 10
의 경우 한 묶음으로 보았을 때 키 차이 == 9 이다.
그리고 이는 내부의 모든 원소들의 키 차이의 합이라 볼 수 있다.

그러면 우리가 할 수 있는 것은 키 차이가 가장 큰 놈들부터 제거 하면서 그룹을 만드는 것이다.

내림차순 정렬

각 인접한 원소들의 키차이를 배열에 저장한 후에 가장 큰 놈들부터 키 차이에서 빼주면서 값을 구하는 것이다. 마지막에 남은 놈들은 각 그룹에서의 키 차이의 합이라고 볼 수 있는 거다.

한정된 값

맨 처음 구한 키 차이 내부에서만 정답이 나온다.
가장 긴 거를 빼는게 어떻게 키 차이의 합을 나타내냐 할 수도 있는데 음..

1 2 3 4 5 6 이거의 키 차이도 5이다.
각 원소들의 키 차이를 보면 1 1 1 1 1
즉 각각의 키 차이의 합이라 볼 수 있다.
이 중에서 가장 큰 것부터 빼버린다면 그 값만큼의 차이는 사라지는 것이다.

import sys

n, k = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

diff = data[-1] - data[0]
idxs = []
for i in range(1, len(data)):
    idxs.append(data[i] - data[i - 1])

idxs.sort(key=lambda x:-x)
for idx in range(1, k):
    diff -= idxs[idx - 1]

print(diff)