[BOJ/C++] 2212: 센서

🏅 GOLD 5

✏️ 최종 솔루션

1. 모든 센서간의 구간을 우선순위 큐에 저장 ➡️ 내림차순 정렬
2. K 개의 구간을 남기기 위해 K-1 개의 구간을 삭제
   ❗️ 이때 구간을 삭제하면서 집중국이 커버할 수 없는 구간이 생기지만 따로 고려할 필요없이 K-1 개 삭제하면 한 개의 센서만을 위한 집중국을 하나 설치했다 치고 최적의 범위를 가지는 K 개의 집중국을 설치할 수 있는 것

📌 self feedback

문제를 이해하지 못했는데 집중국은 센서와 센서 사이의 구간을 의미하는 것이었음

✏️ 최종 code

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

int main() {

    int n,k;
    cin >> n;
    cin >> k;

    vector<int> v;
    for(int i=0;i<n;i++) {
        int c;
        cin >> c;
        v.push_back(c);
    }

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

    priority_queue<int> pq;
    for(int i=1;i<n;i++) {
        pq.push(v[i]-v[i-1]);
    }

    int ans=0;

    int cnt=0;
    while(!pq.empty() && cnt<k-1) {
        pq.pop();
        cnt++;
    }

    while(!pq.empty()) {
        ans+=pq.top();
        pq.pop();
    }

    cout << ans << endl;

}