[C++] 백준 2212번 센서

N개의 고속도로 위에 K개의 집중국을 세웠을 때 집중국의
수신 가능 영역의 길이의 최소값을 출력하는 문제입니다.

이는 N을 정렬한 뒤 K개의 묶음으로 나눠서
묶음 내에서의 최대값 - 최소값의 총 합을 구하면 됩니다.

위의 예제의 경우 정렬을 하면 다음으로 나타낼 수 있습니다.
1 3 6 6 7 9

여기서 각 거리의 차이를 구해줍니다.
 2 3 0 1 2

길이의 최소값을 구해야하므로 가장 긴 거리를 지워줘야 합니다.
집중국의 개수 K - 1개 만큼 가장 긴 길이를 지울 수 있다고 보면 됩니다.
K = 2이므로 1개를 지울 수 있다고 생각했을때 가장 큰 3을 지워줍니다.
그리고 나머지 거리들을 전부 더해주면 수신 가능 영역의 길이의 총 합을 구할 수 있습니다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

int main(int argc, char* argv[])
{
	int n, k;
	int num;
	int s, e;
	int result = 0;
	vector<int> v;
	vector<int> temp;
	priority_queue<pair<int, int> > pq;

	cin >> n >> k;

	for (int i = 0; i < n; ++i) {
		cin >> num;
		v.push_back(num);
	}
	
	sort(v.begin(), v.end());

	for (int i = 1; i < n; ++i) {
		pq.push({ -(v[i] - v[i - 1]), i });
	}

	while (pq.size() >= k) {
		pq.pop();
	}

	while (!pq.empty()) {
		temp.push_back(-(pq.top().second));
		pq.pop();
	}

	sort(temp.begin(), temp.end());
	temp.push_back(-(n));

	s = 0;
	for (int i = 0; i < temp.size(); ++i) {
		e = -temp[i] - 1;
		result += v[e] - v[s];
		s = -temp[i];
	}

	cout << result << endl;

	return 0;
}