백준 2212 센서

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

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

using namespace std;

vector<int> arr;
vector<int> dif;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, k;
    int ans = 0;

    cin >> n >> k;

    arr.resize(n);
    dif.resize(n - 1);

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

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


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

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

    for (int i = 0; i < n - k; i++) {
        ans += dif[i];
    }

    cout << ans;

    return 0;
}

 

1. 문제

n개의 센서의 x좌표상의 위치와 집중국의 개수 k가 주어진다. 이 때, 집중국의 수신 가능 영역의 길이 합의 최솟값을 구하라.

2. 풀이

6
2
1 6 9 3 6 7

이런 입력이 주어졌다고 가정하자. 2개의 집중국의 범위를 다음과 같이 설정하면 5라는 결과가 나온다.

 이를 도출하는 방법은 다음과 같다

1. x좌표가 가장 낮은 센서부터 가장 높은 센서까지를 1개의 큰 집중국으로 본다.
2. 센서 사이의 공간을 큰 것부터 k-1개를 제외한다. 그렇게 되면 k개의 집중국이 되고, 가장 큰 길이가 제거되므로 집중국의 수신 가능 거리는 최소가 된다.

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


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

우선 입력받은 센서의 위치를 정렬하고, 그 차이를 구하여 저장한다.

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

    for (int i = 0; i < n - k; i++) {
        ans += dif[i];
    }

차이를 정렬하고,  n-1개의 차이에서 가장 큰 k-1개의 거리를 제외한 n-k개의 집중국 거리를 더한다. 이를 출력하면 정답을 구할 수 있다.