[BOJ] 15553번: 난로

문제 링크

2018년 JOI 1번 문제다. 난로가 켜져 있는 시간은 N + α 인 것은 자명하다.

그렇다면 α를 알아야 한다. 성냥이 N보다 부족하면 계속 켜놔야 하는 시간을 알아야 하는데 예제를 보면서 계산하는 것이 좀 더 좋을 것 같다.

[예시1] 1 3 6

K가 2일 땐 1 3 사이[1초]나 3 6 사이[2초]를 계속 틀어놔야 할 것이다.

이것에 착안해서 나는 우선순위 큐(오름차순 정렬)를 사용해서

$A_i - A_{i-1} - 1 \neq 0$

(친구들 방문이 이어져 있지 않을 경우) 일 때 간격을 우선순위 큐에 저장을 시키고, 만약 이어져 있는 경우에는 cnt를 증가시켰다.

그래서 우선순위 큐에서 pop을 시키는 횟수는

$T = N - K - cnt$

가 된다.

난로가 켜져 있는 시간의 최솟값을 구해야 하므로 정답은

$N + \sum_{i = 1}^T {pq.pop()}$

이 된다.

#include <bits/stdc++.h>
using namespace std;

int n, k, cnt, arr[100001];
priority_queue<int, vector<int>, greater<int>> pq;

int main()
{
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &arr[i]);
    }

    for (int i = 1; i < n; ++i) {
        if (arr[i] - arr[i - 1] - 1 != 0)
            pq.push(arr[i] - arr[i - 1] - 1);
        else
            cnt++;
    }

    int tmp = n - cnt - k;
    while (tmp-- > 0) {
        n += pq.top();
        pq.pop();
    }
    printf("%d\n", n);
    return 0;
}