백준 #2212 센서

BOJ #2212 - 센서

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

# 문제 분류 그리디

풀이 접근 방법

  1. 맨 왼쪽과 맨 오른쪽을 연결하는 선분 (집중국)이 있다고 하자.
  2. 이 집중국을 적절히 K개로 나누기 위해서는 K-1번의 절단이 필요하다.
  3. 그래서 인접한 센서 사이의 거리를 모두 재서 정렬을 한 후 K-1개까지 빼준다.
  4. 그러면 K개의 가장 최적의 집중국이 남고, 합이 최솟값이 된다.
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

#define endl "\n"

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;

const ll MOD = 1e9 + 7;
const int stMAX = 1 << 18;
const int INF = 1e9;
int N, arr[100010];
int K;
vector<int> v;

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

    sort(arr, arr + N);

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

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

    int result = arr[N - 1] - arr[0];
    for (int i = 0; i < K - 1; i++) {
        // 저격 TC가 있는 듯
        if (v.empty())
            break;
        result -= v.back();
        v.pop_back();
    }

    cout << result;
}