C++ 백준 13164번 : 행복유치원

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

13164번: 행복 유치원

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

---

풀이

바로 뒷 사람과 키 차이를 따로 저장해서 K-1만큼 큰 것부터 제외해서 답을 구했다. 

 

EX)  원생 수 : 5  , 조 2개

 

 원생 : 1  3  5  6  10

 키 차이 : 2 2 1 4

여기서 조 2개니까 제일 큰 4을 제외하고 나머지를 다 합한 5가 답이 된다. (1 3 5 6) (10) 조가 이렇게 나뉜다.

- (1)(3 5 6 10) = 7

- (1 3)(5 6 10) = 7

- (1 3 5)(6 10) = 8

- (1 3 5 6)(10) = 5 

최소인 것을 확인할 수 있다.

---

#include <bits/stdc++.h>
using namespace std;
int child[300001];
vector <int> interval;
int main() {
    int N, K;
    cin >> N >> K;

    for (int i = 0; i < N; i++) {
        int tmp;
        cin >> tmp;
        child[i] = tmp;
    }
    if (K == 1) { // K==1일 경우
        cout << child[N-1] - child[0] << endl;
        return 0;
    }
    for (int i = 1; i < N; i++) { // 인접한 차이 값 저장
        interval.push_back(child[i] - child[i - 1]);
    }
    sort(interval.begin(), interval.end());

    
    int sum = 0;
    for (int i = 0; i < N- K ; i++) { // 제일 많이 차이나는 것 제외
        sum += interval[i];
    }
    cout << sum << endl;
    return 0;
}