[백준] 2212 - 센서

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

2212번: 센서

센서 정보를 입력받고 이를 오름차순으로 정렬해 줍니다. 그러면 일직선상에 센서가 나열되고 이를 집중국의 개수 K 개의 집합으로 만드는데 이 길이의 최소값을 구하는 것이 목적입니다. 이를 계산하기 위해 인접한 센서끼리의 길이를 구해 주고 이를 오름차순으로 나열해줍니다. 그리고 이를 1번째부터 n - k 번째까지 더하면 답이 됩니다. 그 이유를 아래 그림으로 설명하자면

인접한 센서끼리의 거리, 저는 벡터 v2에 저장하여 오름차순으로 정렬해줍니다. 이를 k 개의 집합으로 묶어야 하니 빨간색 줄을 k - 1개 끊는다고 생각합니다. 그렇게 하면 위 그림과 같이 1번째부터 n - k 번째 거리까지 더하면 답이 됩니다. 예외로 k 가 n 이상일때는 n 집합만큼 묶으면 모든 길이가 0이 되므로 따로 처리해줍니다.

 

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

vector<int> v1, v2;
int n, k, ans;

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        v1.push_back(num);
    }

    if (n <= k)
        cout << "0\n";
    else {
        sort(v1.begin(), v1.end());
        for (int i = 0; i < v1.size() - 1; i++)
            v2.push_back(abs(v1[i + 1] - v1[i]));
        sort(v2.begin(), v2.end());

        for (int i = 0; i < n - k; i++)
            ans += v2[i];
        cout << ans << "\n";
    }

    return 0;
}