[Algorithm] 백준 13164 행복 유치원 - C++

13164번: 행복 유치원

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

int n, k;
int kids[300001];

int main(){
    // init 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // input
    cin >> n >> k;

    if(k == n){
        cout << "0\n";
        return 0;
    }

    for(int i = 0; i < n; i++)
        cin >> kids[i];
    
    // solve
    vector<int> differences;
    for(int i = 0; i < n-1; i++)
        differences.push_back(abs(kids[i] - kids[i+1]));
    
    sort(differences.begin(), differences.end());

    int answer = 0;
    for(int i = 0; i < n-k; i++)
        answer += differences[i];

    cout << answer << '\n';
}

---

 그리디 중에서 규칙을 알아내면 괜찮은 문제였습니다. 일단  n == k 가 true 인 경우에는 1인 1 그룹이니 이를 위한 출력을 해준 뒤 그 외의 경우 차이를 순서대로 대입한 뒤 낮은 순에서 n-k 만큼 그룹을 지어주면 됩니다. 남은 차이들은 다른 그룹으로 분류를 해서 생산 단가를 피하는 전략입니다.