[백준-13164] 행복 유치원

모든 경우이 수를 다 보는 것은 1초의 제한시간과 30만의 입력값을 보았을 때 당연히 되지 않는구나~ 라고 느껴야 한다.

때문에 뭔가 다른 방법을 생각해야 한다. 이 문제의 경우는 인접한 수끼리의 차를 정렬한 뒤 N-K 만큼 앞부터 원소를 고르는 식으로 집합을 생각하면 간단하다. 이와 같이 구현만 하면 문제는 간단히 풀린다.

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
deque<int> arr;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a, b;
    cin >> a >> b;
    
    int cur, prev = 0;
    for (int i = 0; i < a; i++) {
        cin >>  cur;
        if (prev == 0) {
            prev = cur;
            continue;
        }
        else {
            arr.push_back(cur - prev);
            prev = cur;
        }
    }

    sort(arr.begin(), arr.end());

    LL res = 0;
    for (int k = 0; k < a-b; k++) {
        int cx = arr.front();
        arr.pop_front();
        res += cx;
    }
    cout << res;
    // 2 2 1 5
    return 0;
}

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

13164번: 행복 유치원