백준 13164. 행복 유치원

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

13164번: 행복 유치원

 

하나의 그룹의 티셔츠 비용은 가장 큰 원생 - 가장 작은 원생이다.

그런데 만약 인접한 원생의 차를 모두 구해놓고 보면, 티셔츠 비용은 인접한 원생의 차들의 합이기도 하다.

 

예를들어 입력값이 

1 3 5 6 10 이라면 인접한 원생의 차는

 2  2 1  4  이다. 

 

만약 (3,5,6)이 한 그룹이라면 티셔츠 비용은 6-3=3 이기도 하지만,

인접한 원생의 차들의 합인 2+1=3 이기도 하다.

 

그룹에 한명만 속해있다면 티셔츠 비용은 0이므로,

최솟값을 구하려면 인접한 원생의 차가 최대인 부분을 그룹의 경계로 설정해주면된다.

 

즉 인접한 원생의 차 : 2 2 1 4를 정렬해서 4 2 2 1

가장 큰 k-1개의 값을 제외한 합이 답이다.

 

 

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

int n, k;
vector<int> v;

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

    cin >> n >> k;
    v.resize(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];

    // 인접한 원생 둘의 키의 차
    vector<int> sub;
    for(int i = 0; i < n-1; i++)
    {
        int subtraction = v[i+1]-v[i];
        sub.push_back(subtraction);
    }

    // 내림차순 정렬
    sort(sub.begin(), sub.end(), greater<>());

    // 가장 큰 k-1 (경계가되는)을 제외한 나머지의 합
    int ans = 0;
    for(int i = k-1; i < n-1; i++)
        ans += sub[i];

    cout << ans;

}