[Algorithm]Baekjoon 2212번 :: 센서

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

2212번: 센서

 
 
using namespace std;
 
int n, k, input;
vector<int> arr;
vector<int> distanceGaps;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> k;
 
    if (k >= n)
    {
        cout << 0;
        return 0;
    }
 
    for (int i = 0; i < n; ++i)
    {
        cin >> input;
        arr.push_back(input);
    }
 
    sort(arr.begin(), arr.end());
    
    int prevPosition = arr[0];
 
    for (int i = 1; i < arr.size(); ++i)
    {
        distanceGaps.push_back(arr[i] - prevPosition);
        prevPosition = arr[i];
    }
 
    sort(distanceGaps.rbegin(), distanceGaps.rend());
 
    int answer = 0;
    for (int i = k - 1; i < distanceGaps.size(); ++i)
    {
        answer += distanceGaps[i];
    }
 
    cout << answer;
}
 
 

 

집중국을 설치했을 때 모든 센서를 커버할 경우의 최소커버길이값을 구하는 문제이다.

집중국은 최대 k개 설치할 수 있고, 집중국의 개수 k개가 센서개수 n개보다 같거나 많으면 각 센서마다 다 설치해버리면 되기때문에 그냥 0을 출력하면 된다.

 

센서위치는 중구난방으로 주기 때문에 먼저 오름차순정렬을 한번 해준다.

이후 첫번째 센서부터, 바로 오른쪽에있는 센서까지의 거리값을 다 저장해준다. (distanceGaps)

그리고 내림차순으로 정렬을 해준다.

 

그러면 distanceGaps에는 거리값이 가장 큰것부터 들어있을 것이다. 이 거리값들은, 집중국을 한개 설치할때마다 건너뛸 수 있는 값이다. 

거리가 아주 먼 센서가 있다고 하더라도, 집중국을 설치해버리면 아예 사라지는 값이 된다. 거리가 먼 센서에 설치해버리면 되니까.