행복 유치원 13164

문제

접근 방법

각 숫자는 차이로 연결됐다고 생각하면 된다.
1, 3, 6, 7이면 2, 3, 1의 차이로 연결된 것이다.
1개의 조라면 2+3+1이고
2개의 조라면 1개의 연결을 끊어 2+1이다.
이런 식으로 접근하면 되는 것이다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, K, sum;
vector<int> v, gap;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K;
    v = vector<int>(N);
    cin >> v[0];
    for (int i = 1; i < N; ++i)
    {
        cin >> v[i];
        gap.push_back(v[i] - v[i - 1]);
    }
    sort(gap.begin(), gap.end());
    while (--K)
        gap.pop_back();
    for (int i : gap)
        sum += i;
    cout << sum;
    return 0;
}

풀이

우선순위 큐로 격차가 가장 낮은 값부터 그룹 짓는 방식을 생각했다.
하지만 그룹이 만들어진 후 다시 갱신해야 하는데 그 부분이 너무 복잡하다고 생각했다.

다른 사람 풀이를 확인해 보니 격차가 가장 큰 값부터 지우면 되는 것이었다.
연결하고 있는 요소를 끊어줌으로써 그룹을 나누는 것이었다.

더 생각해 보고 다른 사람의 풀이를 봤어야 했는데 싶었다.