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

그리디 문제이다. 조를 나누는 문제이므로 K-1의 칸막이를 설치한다고 생각할 수 있다.

직관: 한 조의 차이가 가장 작아야 하므로 일단 가장 차이가 큰 곳에 칸막이를 우선적으로 설치하면 차이가 최대가 될 것 같다.

 

반례: 가정 결론 도출

코드

#include<iostream>
#include<algorithm>
#define F first
#define S second

using namespace std;

int N, K, h[300000], sum;
pair<int, int> dif[300000];
bool devide[300000];

int main(void){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> N >> K;
    for(int i=0; i<N; i++) cin >> h[i];
    for(int i=0; i<N-1; i++) dif[i] = {h[i+1] - h[i], i};
    sort(dif, dif + N-1, greater<pair<int, int>>());
    int j = K-1;
    //for(int i=0; i<N-1; i++) cout << dif[i].first << " ";
    for(int i=0; i<K-1; i++) devide[dif[i].S] = true;

    int st = 0;
    devide[N-1] =  true;
    for(int en=0; en<N; en++){
        if(devide[en]) {
            sum += h[en] - h[st];
            st = en + 1;
        }
    }
    cout << sum;


    return 0;
}