백준 2212번: 센서 - 그리디 C++

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

2212번: 센서

1.문제설명

각 센서들의 좌표를 정렬하고 각 좌표간의 간격을 구해서 다시 정렬하여

 

가장 긴 간격을 k의 개수에 따라서 알맞게 빼주면 답을 구할 수 있습니다.

 

좌표는 중복된 값이 들어올 수 있으므로 set 자료구조를 이용하면 편하게 구할 수 있습니다.

 

 

6
2
1 6 9 3 6 7

 

백준 2212 설명

위 예제에서는 센서간의 간격의 길이가 3이 제일 길기 때문에

 

전체 간격의 길이인 9-1=8에서 3을 빼주면

 

나머지 센서를 다 포괄할 수 있게 됩니다.

 

 

---

 

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, k;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	set<int> num;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		num.insert(tmp);
	}

	n = num.size();

	if (n <= k) {
		cout << 0;
		return 0;
	}
	vector<int> v(num.begin(), num.end());

	vector<int> interval;

	int ans = 0;
	for (int i = 0; i < n - 1; i++) {
		ans += v[i + 1] - v[i];
		interval.push_back(v[i + 1] - v[i]);
	}

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

	
	for (int i = 0; i < k-1; i++) {
		ans -= interval[interval.size() - 1 - i];
	}
	cout << ans << '\n';


	

	return 0;
}

백준 2212번 그리디