[c++] 백준 13164 행복 유치원

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

13164번: 행복 유치원

#include<bits/stdc++.h>
using namespace std;
vector<int> child, divide;
vector<pair<int,int>> dist;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //입력 받기
    int n,k; cin>>n>>k;
    for(int i=0; i<n; i++){
        int a; cin>>a;
        child.push_back(a);
    }
    //이웃한 아이들의 키 차이 저장
    for(int i=1; i<n; i++)
        dist.push_back({child[i]-child[i-1],i});
    //키 차이가 큰 곳 부터 k-1번 자른다
    //(자르는 위치 저장)
    sort(dist.begin(), dist.end());
    for(int i=n-2; i>=n-k; i--){
        divide.push_back(dist[i].second-1);
    }
    //자른 위치를 불러오며 1번째 키와 자른 부분의 키의 차를 ans에 더한다
    int index=0, ans=0;
    for(auto i : divide){
        ans+=child[i]-child[index];
        index = i+1;
    }
    //마지막 연산 처리
    ans+=child[n-1]-child[index];
    cout << ans;
    return 0;
}