백준 2212번: 센서

[문제 링크]

2212번: 센서

---

문제를 이해하는데 있어 어려움을 겪었던 문제였다.

 

일단, 고속도로에 위치한 센서의 좌표가 정렬되지 않은 상태로 주어지기 때문에 이를 오름차순으로 정렬해야한다.

 

그리고 집중국의 개수 K가 센서의 개수 N보다 크거나 같으면 센서마다 배치해주면 되지만, 작을 경우 집중국의 수신 가능 영역을 최소로 하기 위해서는 센서 사이의 거리가 긴 센서들을 하나의 집중국에서 연결하는 것을 피해야 한다.

 

따라서, 인접한 센서들 간의 거리를 구한 다음, 이를 오름차순 정렬하여 거리 차이가 작은 센서들부터 연결하도록 구현하였다.

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int Greedy(vector<int>& v, int N, int K)
{
	if (K >= N) return 0;

	sort(v.begin(), v.end());

	vector<int> dist(N - 1);
	for (int i = 0; i < N - 1; i++)
		dist[i] = v[i + 1] - v[i];

	sort(dist.begin(), dist.end());

	int ret = 0;
	for (int i = 0; i < N - K; i++)
		ret += dist[i];

	return ret;
}

int main(void)
{
	int N;
	cin >> N;

	int K;
	cin >> K;

	vector<int> arr(N);
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	cout << Greedy(arr, N, K) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 131 day