풀이
문제를 조금 다르게 생각해 보자.
일직선 상의 정수 좌표 n개가 주어졌을 때, k개 이하의 구간으로 모든 좌표를 묶어야 한다. 이 때, 구간 길이의 합을 최소로 하여라.
인접한 좌표 사이의 길이를 모두 구해놓고 생각해 보자.
상대적으로 긴 구간을 k개의 구간에 포함시키는 것은 손해이다.
k개의 구간을 나눌 수 있다는 말은 구간들 중에서 k개의 길이를 답에 포함시키지 않을 수 있다는 말과 같다.
구간의 길이를 모두 구해 정렬하고 가장 작은 n-k개의 구간을 선택해 주자.
우선순위 힙으로도 풀 수 있다.
코드
#include <cstdio>
#include <algorithm>
int n, k, ans, a[100010], b[100010];
int main() {
scanf("%d %d %d", &n, &k, &a[0]);
for (int i = 1; i < n; i++) {
scanf("%d", &a[i]);
b[i-1] = a[i]-a[i-1];
}
std::sort(b, b+n-1);
for (int i = 0; i < n-k; i++) {
ans += b[i];
}
printf("%d", ans+k);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이