[백준 2212] 센서

김동근·2021년 2월 15일
0
post-thumbnail

문제

백준 2212

유형

  • 그리디

풀이

생각의 전환이 필요했던 문제라고 생각한다. 일단 정렬 후 인접한 센서의 거리 차이를 전부 구하고 거기서 제일 큰 k-1개의 거리를 제거하면 정답을 얻을 수 있었다.

만약 예제와 같이 k가 2이고 주어지는 센서의 위치가 1 6 9 3 6 7이라면 중복되는 값은 빼고 정렬 후 인접한 센서 거리 차이를 구하면 2 3 1 2이고 다시 정렬하면 1 2 2 3이 된다. 거기서 k-1개를 빼면 1 2 2가 되고 이것들의 합이 답이 된다.

왜 이러한 풀이가 가능하냐면 이 문제를 k개 구간을 만드는 문제로 생각해보면 n-1개의 센서 거리차에서 k-1개를 제외하면 k개의 구간이 나오는데 여기서 각 구간의 합이 최소가 되려면 k-1개를 제외할 때 큰 순서대로 제외하면 최쇠값을 구할 수 있기 때문이다.

코드

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

int n, k;
set<int> s;
vector<int> v;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int x; cin >> x; s.insert(x);
	}
	n = s.size();
	for (auto iter = s.begin(); iter != s.end(); iter++) v.push_back(*iter);

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

	sort(v.begin(), v.begin() + n - 1);
	long long ans = 0;
	for (int i = 0; i < n - k; i++) ans += v[i];

	cout << ans;
	return 0;
}
profile
김동근

0개의 댓글