[백준 13164번] 행복 유치원

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

행복 유치원 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	376	237	181	63.066%

문제

행복 유치원 원장인 태양이는 어느 날 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

UCPC를 대비해서 문제를 하나씩 풀고 있다. 63%라서 얕봤는데 꽤나 생각이 필요한 문제였다.

dp로 풀까 생각했는데 유치원생 수가 자그마치 30만명이나 되서 불가능하다는 생각이 들었고,

유치원생들이 "서로 인접해 있어야 한다"는 조건으로 접근해서 문제를 해결했다.

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int N, K, M;
unsigned long cnt;
pair<int, int> child[300001], ary[30001];
bool flag[300001], line_flag[300001];
 
int main() {
 
    ios::sync_with_stdio(false);
 
    cin >> N >> K;
 
    for (int i = 0; i < N; i++) {
        cin >> child[i].first;
        child[i].second = i;
    }
    if (N == K) {
        cout << "0";
        return 0;
    }
    
    for (int i = 0; i < N-1; i++) {
        ary[i].first = child[i + 1].first - child[i].first;
        ary[i].second= i;
    }
 
    sort(ary, ary + N - 1);
    
    for (int i = 0; i < N - K; i++) {
        if (!line_flag[ary[i].second]) {
            flag[ary[i].second] = true;
            flag[ary[i].second + 1] = true;
            line_flag[ary[i].second] = true;
            cnt += ary[i].first;
            M++;
        }
    }
 
    for (int i = N - K; i < N; i++) {
        if (N - M == K) break;
        if (!line_flag[ary[i].second]) {
            M++;
            cnt += ary[i].first;
            flag[ary[i].second] = true;
            flag[ary[i].second + 1] = true;
        }
    }
 
    cout << cnt;
 
    return 0;
}