[Gold 5] 2212번 센서

https://www.acmicpc.net/problem/2212

2212번: 센서

 

이 문제는 그리디 알고리즘을 활용해서 해결할 수 있다.

센서들 값을 입력받고 배열을 정렬한다.

센서들의 값이 정렬되었으므로 센서들의 차이를 통해 거리를 계산하고 배열에 삽입한다.

그후 거리 배열을 K-1만큼 pop한 후 배열의 크기를 출력한다.

 

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

int N,K;

bool sorter(int a, int b) {
	return a > b;
}
int main() {
	cin >> N;
	cin >> K;

	vector<int> sensors;
	for (int i = 0; i < N; i++) {
		int sensor;
		cin >> sensor;
		sensors.push_back(sensor);
	}
	sort(sensors.begin(), sensors.end());

	vector<int> distance;
	for (int i = 0; i < N - 1; i++) {
		distance.push_back(sensors[i + 1] - sensors[i]);
	}
	if (distance.empty()) {
		cout << 0 << '\n';
		return 0;
	}
	sort(distance.begin(), distance.end());

	for (int i = 0; i < K - 1; i++)
		distance.pop_back();

	int result = 0;
	for (int i = 0; i < distance.size(); i++)
		result += distance[i];

	cout << result << '\n';
}