[ 백준 / C++ ] 2212 : 센서

[ 문제 ]

 

2212번: 센서

 

[ 접근방법 ]

 

일단 집중국을 최대한 많이 설치해야 수신 가능한 영역 길이의 합이 작게 나온다.

 

예제 1은 집중국을 2, 7에 설치할 때 최솟값이 나온다. (다른 방법도 있음)

 

1, 3에     위치한 센서는 2에 위치한 집중국에 연결되고,

6, 7, 9에 위치한 센서는 7에 위치한 집중국에 연결된다.

 

1 ~ 3, 6 ~ 9 각각을 묶음으로 생각하면 3 ~ 6이 버려지는 구간인데,
이 버려지는 구간을 최대로 설정하면 원하는 최솟값을 구할 수 있다.

 

즉, 센서 사이의 거리가 큰 구간을 버려지는 구간으로 설정하면 원하는 최솟값을 구할 수 있다.

 

[ 소스코드 ]

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(const int &a, const int &b){
    return a > b;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, k, ans;
    cin >> n >> k;

    vector<int> pos(n);
    for(int i = 0; i < n; i++)cin >> pos[i];
    sort(pos.begin(), pos.end());

    vector<int> dist;
    for(int i = 0; i < n - 1; i++)dist.push_back(pos[i + 1] - pos[i]);
    sort(dist.begin(), dist.end(), cmp);

    ans = pos.back() - pos.front();
    for(int i = 0; i < min(n, k) - 1; i++)ans -= dist[i];

    cout << ans;

    return 0;
}