[13164] 행복 유치원(C++)

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다.

각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다.

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

최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다.

태양이를 도와 최소의 비용을 구하자.

 

 

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다.

다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다.

태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다.

원생의 키는 109를 넘지 않는 자연수이다.

 

 

출력

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

 

 

해결 방법

이 문제를 보고 가장 먼저 떠올릴 수 있는 방법은 그룹을 구분할 막대기 K개를 (n-1)의 위치 중 어디에 둘지 고르는 것이다.

하지만 n이 최대 300,000이기 때문에 이렇게 하면   (n-1)Ck > 1억 으로 시간초과가 나게 된다.

그래서 O(n) 또는 O(nlogn)의 방법을 찾아야 한다.

 

잘 생각해보자.

문제의 목표는 각 그룹의 (최대 키 - 최소 키)가 최소가 되게 하는 것이므로 인접한 학생들 간에 키 차이가 많이 나는 곳을 중심으로 그룹을 구분지어야 한다.

그래서 학생들을 탐색하면서 <나의 오른쪽에 있는 학생과 나의 키 차이, 나의 인덱스> 정보를 vector에 저장한뒤 키 차이를 기준으로 내림차순 정렬을 해준다. 

다음으로, k개의 그룹을 생성하기 위해 vector의 첫번째 원소부터 (k-1)개의 학생을 뽑는다. 이 학생의 오른쪽에 그룹 구분 막대기를 두는 셈이다.

마지막으로 뽑힌 학생들을 기준으로 그룹별 (최대 키 - 최소 키)를 계산하고 이 값을 전부 더하면 정답이 된다.

이 문제가 그리디인 이유는 <키 차이, 인덱스>를 저장한 vector에서 키 차이가 가장 많이 나는 인덱스 (k-1)개를 맨 앞의 원소부터 차례대로 선택했기 때문이다. 위에서 말한 것처럼 이 문제의 목표는 키 차이를 최소화 하는 것이기 때문에 나와 내 오른쪽 학생간에 키 차이가 많이 난다면 이 둘을 다른 그룹으로 구분짓는 것! 

 

 

내 코드

// [13164] 행복 유치원
// 그리디
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool cutPoint[300001];
int n, k, height[300001];
vector<pair<int, int>> candidateCutPoint; // <키 차이, idx>

void input()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> height[i];
    }
}

void setGroup()
{
    for(int i = 1; i <= n-1; i++) {
        candidateCutPoint.push_back(make_pair(height[i+1] - height[i], i));
    }
    sort(candidateCutPoint.rbegin(), candidateCutPoint.rend());
    for(int i = 0; i < k - 1; i++) {
        cutPoint[candidateCutPoint[i].second] = true;
    }
}

int getCost()
{
    int cost = 0, pre = 1;
    for(int i = 1; i <= n; i++) {
        if(cutPoint[i]) {
            cost += (height[i] - height[pre]);
            pre = i + 1;
        }
    }
    cost += height[n] - height[pre];
    return cost;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    input();
    setGroup();
    cout << getCost() << '\n';

    return 0;
}