백준 2212 센서 (C++)

2212번: 센서

그리디를 이용한 문제이다. 집중국이 K 개라면 집중국 사이의 공백은 K - 1개가 된다. 주어진 센서 간의 거리를 구해 저장해준 후 이를 내림차순으로 정렬해 공백 개수인 K - 1 개를 제외한 나머지의 합을 출력해주면 된다.

• 3 6 7 8 10 12 14 15 18 20 일 경우
• 센서 간의 거리는 3 1 1 2 2 2 1 3 2, 내림차순 시 3 3 2 2 2 2 1 1 1
• K - 1만큼 제외하면 2 2 1 1 1, 합은 7이다.

사실 이 문제는 지문을 이해하는 것이 많이 어려웠다. 실제로 질문하기 탭을 보면 지문이 어렵다는 사람이 많았다. 지문을 바로 이해하는 것도 굉장히 중요하다. 빠르게 이해하도록 노력하자.

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

using namespace std;

int N, K, result = 0;
vector<int> v;
vector<int> d;

void solution() {
    sort(v.begin(), v.end());

    for (int i = 1; i < v.size(); i++) {
        d.push_back(v[i] - v[i - 1]);
    }

    sort(d.rbegin(), d.rend());

    for (int i = K - 1; i < d.size(); i++) {
        result += d[i];
    }

    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> K;

    int a;
    for (int i = 0; i < N; i++) {
        cin >> a;
        v.push_back(a);
    }

    solution();

    return 0;
}