풀이
각각의 좌표들을 정렬해보자.
그리고 인접한 좌표들의 거리 차이를 구해보자.
그리고 그 거리 차이를 다시 정렬해보자.
k개의 집중국, 다시 말해 k개의 직선을 놓는다면
k-1개의 빈 공간(?)이 생기게 만들 수 있다.
그러므로 방금 정렬한 거리 차이 중에서 가장 큰 값을 k-1개 고르면
집중국이 차지하는 영역(?)의 합이 최소가 될 것이고
답을 구할 수 있다 (!!)
코드
#include <stdio.h>
#include <algorithm>
int n, k, ans, a[10001];
int main() {
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
std::sort(a, a + n); ans = a[n - 1] - a[0];
for (int i = n - 1; i > 0; i--) a[i] -= a[i - 1];
std::sort(a + 1, a + n);
for (int i = n - 1; i > 0 && --k; i--) ans -= a[i];
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이