행복 유치원

알고리즘 구분 : 그리디, 정렬

문제

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

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

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

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

예제 입력 1
5 3
1 3 5 6 10
예제 출력 1
3
힌트
1조: 1, 3
2조: 5, 6
3조: 10

문제 풀이

K개의 조로 나눈다는 의미를 먼저 생각해보면, K - 1개의 경계선이 생긴다는 의미이다.
이미 입력에서 오름차순으로 주어진다는 것이 문제에 적혀 있기 때문에, 각 원생 간 키 차이를 저장하는 differ 배열을 만들어 입력값을 받는 과정에서 정보를 저장하고, 이 중 가장 키 차이를 크게 가지고 있는 원생들 간 거리 위치를 K - 1개만큼 찾아주면 된다.

예제로 설명을 하자면,
1 3 5 6 10으로 줄 서 있을 때, 각 원생 별 차이는 2, 2, 1, 4이다. K == 3이므로, 2개의 경계선을 찾아야 하는데, 이는 가장 큰 차이를 가지고 있는 4와 2를 제거해야 한다는 의미가 된다.
그렇게되면 전체 차이의 합은 2 + 2 + 1 + 4 = 9이였지만, 4와 2를 뺀 결과 값인 3이 답이 된다.

소스 코드

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"

int n, k, result;
int height[300001];
vector<int> differ;
void solve();

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

    result = 0;

    cin >> n >> k;
    for(int i = 0; i < n; i++) {
        cin >> height[i];
        if(i >= 1) {
            differ.push_back(height[i] - height[i - 1]);
            result += (height[i] - height[i - 1]);
        }
    }

    solve();

    return 0;
}

void solve() {
    sort(differ.begin(), differ.end(), greater<int>());

    for(int i = 0; i < k - 1; i++) {
        result -= differ[i];
    }

    cout << result << endl;
}

• 문제 출처 :
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.