백준 13164번 행복 유치원

🔒문제 url

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

🔑알고리즘

$k$개의 조를 만들기 위해서는 $k - 1$개의 경계선을 나누어야 한다.
1번과 2번 사이에 경계선을 두면, 즉 1번과 2번을 다른 조에 편성하면 둘 사이의 키 차이는 총 비용에서 제외된다.

인접한 원생 사이의 모든 키 차이를 구한 뒤 총합을 구하고, 가장 큰 $k-1$개의 값을 뺀 값이 답이 된다.

🐾부분 코드

cin >> n >> k;
for (int i = 0; i < n; i++)
{
    cin >> tall[i];
    if (i)
    {
        pq.emplace(tall[i] - tall[i - 1]);
        ans += tall[i] - tall[i - 1];
    }
}

<입력 및 총합>
인접한 원생 사이의 모든 키 차이의 합을 구하고, 상위 $k - 1$개를 빼기위해 우선순위 큐에 담는다.

🪄전체 코드

#include <bits/stdc++.h>

using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

int n, k;
int tall[300001];
priority_queue<int> pq;
int ans = 0;

void INPUT()
{
    IAMFAST
    cin >> n >> k;
    for (int i = 0; i < n; i++)
    {
        cin >> tall[i];
        if (i)
        {
            pq.emplace(tall[i] - tall[i - 1]);
            ans += tall[i] - tall[i - 1];
        }
    }
}


void solution()
{
    for (int i = 0; i < k - 1; i++) ans -= pq.top(), pq.pop();
    cout << ans;
}


int main()
{
    INPUT();
    solution();
}

🥇문제 후기

Greedy 특징, (고민 = 2시간) (코드 구현 + 포스팅 = 5분)