백준 13164 행복 유치원

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

13164번: 행복 유치원

 

 

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

#define INF 987654321

using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n, k;
    int ans;

    cin >> n >> k;

    vector<int> ch(n);

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

    ans = ch[n - 1] - ch[0];

    vector<int> cost;

    for (int i = 1; i < n; i++) {
        cost.push_back(ch[i] - ch[i - 1]);
    }

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

    for (int i = k - 1; i >= 1; i--) {
        ans -= cost[n - 1 - i];
    }


    cout << ans;


    return 0;
}

 

cost[i]=ch[i+1]-ch[i]로 정의해보자

k=1일 때: ans=ch[n-1]-ch[0]=ch[n-1]-ch[n-2]+ch[n-2]-ch[n-3]+...+ch[1]-ch[0]=cost[n-2]+cost[n-3]+...+cost[0]가 된다.

여기서 이를 둘로 나눈다면 

ans=ch[n-1]-ch[r]+ch[r-1]-ch[0]=(cost[n-2]+...+cost[r])+(cost[r-2]+...+cost[0])

즉, cost[r-1]=cost[r]-cost[r-1]이 빠진다.

최소의 비용이 사용되어야 하므로 cost를 정렬하여 큰 값부터 빼야하고, k개의 조로 나누려면 k-1번 나눠야 하므로 k-1개의 수를 빼야한다.

 

요약하자면, k=1일 때의 전체 cost를 구하고, 두 학생 간의 키 차이가 큰 수부터 k-1개만큼 빼면 정답을 출력할 수 있다.