[백준 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;
}
Author And Source
이 문제에 관하여([백준 2212] 센서), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@asdsa2134/백준-2212-센서저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)