13164 행복 유치원

 

헉 대박대박 세상에 

혼자 로직 떠올렸음

풀었다니 뿌듯해서 기분 째진다 

 

처음에 최대 최소라 해서 파라메트릭 서치...?싶었는데 구간이 정해져있지 않아서 좀 힘들겠다 싶었음

이분탐색으로도 안 될 것 같고

 

그 다음 생각난게 부분합인거야 

저건 부분합이 아니긴 하지만 전에 부분합으로 미분개념? 해서 두 값의 변화량 이런게 떠올랐음

 

그래서 보니깐 두 값의 변화량이 가장 큰 걸 기준으로 나누면 최소겠구나! 싶어서 그렇게 로직 짰다.

 

코드 돌아가는 건

 

1. 변화량을 저장한다

2. 정렬한다 (내림차순으로)

3. 가장 큰 거 k-1개 부터 끝까지 더한다

4. 해결~

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MOD 1000000009

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;


int     main()
{
    int n, k;
    scanf("%d %d", &n, &k);

    vector<int> v(n);
    for (int i = 0; i < v.size(); i++)
        scanf("%d", &v[i]);

    vector<int> diff(n - 1);
    for (int i = 0; i < n - 1; i++)
        diff[i] = v[i + 1] - v[i];

    sort(all(diff), greater<int>());

    int sumv = 0;
    for (int i = k - 1; i < diff.size(); i++)
        sumv += diff[i];
    cout << sumv << endl;

    return 0;
}