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

문제

13164번: 행복 유치원

 

코드

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

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N, K; cin>>N>>K;
    vector<long long int> v(N), cost(N-1);
    
    for(int i=0; i<N; i++) cin>>v[i];
    
    sort(v.begin(), v.end());
    
    for(int i=1; i<N; i++) cost[i-1] = v[i] - v[i-1];
    
    sort(cost.begin(), cost.end());
    
    long long int ans = 0;
    for(int i=0; i<N-K; i++) ans += cost[i];
    
    cout<<ans;
}

 

풀이

저는 처음에 몇 명씩 묶어야 할지 N과 K를 가지고 어떠한 규칙을 찾아 해결하려고 했지만 "조별로 인원수가 같을 필요는 없다."라는 조건 때문에 해당 방법은 답이 없다는 것을 알게 되어 다른 방법으로 접근했습니다.

"조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다."

즉, 옆사람과의 키 차이를 저장한 뒤, 그 키 차이에서 큰 순서대로 K개만큼 제외해준 다음 제외되지 않은 키 차이들을 전부 더한다면 이것이 조별로 드는 비용이 됩니다. K만큼 제외하는 이유는 키 순서대로 정렬을 했을 경우, 키가 큰 원생들은 혼자 그룹을 만들었을 때 비용이 발생하지 않기 때문입니다.

예시로 한번 설명해 보겠습니다.

5 2
2 5 6 7 9

위와 같은 입력이 주어졌을 때 (2), (5, 6, 7, 9)로 묶으면 최소비용인 4가 나오게 됩니다.

3 1 1 2

위 입력을 가지고 옆 사람의 키 차이를 구하면 위와 같습니다.

1 1 2 3

키 차이를 오름차순으로 정렬하면 위와 같습니다.

따라서 값이 크기에 혼자 그룹을 만들어 더하지 않아도 되는 (N-K) 개를 제외하고 더하기에 1+1+2를 더한 것이 (2), (5,6,7,9)로 나눈 것과 같은 값이 나오게 되어 정답이 됩니다.