백준 13164 행복 유치원 (C++)

13164번: 행복 유치원

그리디를 이용한 문제이다. 조마다 차이가 최소가 되도록 조를 만들어야 하므로 우선 조원끼리의 차이를 구해주고 오름차순으로 정렬을 해준다. 조에는 인원이 한명만 있을 경우 차이가 0이 되기때문에 값을 구할 필요가 없다. 각 조마다 먼저 한명씩 넣어주면 남은 인원은 N - K가 된다. 즉 N - K가 들어가게 되는 조는 두명 이상이 되므로 N - K만큼만 차이의 합을 구해주면 된다. 오름차순으로 정렬한 차이들의 합을 구하고 이를 출력해주었다. 쉽게 풀 수 있었던 문제였다.

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

using namespace std;

int N, K, result = 0;
int A[300000];
vector<int> v;

void solution() {
    for (int i = 1; i < N; i++) {
        int dif = A[i] - A[i - 1];
        v.push_back(dif);
    }

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

    for (int i = 0; i < N - K; i++) {
        result += v[i];
    }

    cout << result;
}

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

    cin >> N >> K;

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

    solution();

    return 0;
}