[BOJ] 난로 15553 C++ 풀이

문제

구사과의 방에는 난로가 하나 있다. 구사과는 절약 정신이 투철하기 때문에, 방에 혼자 있을 때는 난로를 되도록 켜지 않는다. 구사과는 방에 친구가 왔을 때는 항상 난로를 켠다.

오늘은 N명의 친구들이 구사과의 집에 방문하는 날이다. 구사과는 친구들을 쉽게 구분하기 위해 1부터 N까지 번호를 매겼다. i번째 친구는 구사과의 방에 시간 Ti에 도착하고, 시간 Ti+1에 나간다. 구사과의 방은 좁기 때문에, 한 번에 한 명만 방문할 수 있다. 즉, 방안에는 항상 구사과를 포함해 2명 이하의 사람만 있게 된다.

구사과는 난로를 아무 때나 켤 수 있고, 끌 수 있다. 난로를 켜려면 성냥을 이용해야 한다. 오늘 구사과는 총 K개의 성냥을 가지고 있다. 따라서, 최대 K번 난로를 켤 수 있다. 가장 처음에 난로는 꺼져있다.

구사과는 난로가 켜져 있는 시간을 최소로 하려고 한다. 구사과의 친구들이 도착하는 시간과 가지고 있는 성냥의 개수가 주어졌을 때, 난로가 켜져 있는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 구사과의 집을 방문하는 친구의 수 N (1 ≤ N ≤ 100,000), 구사과가 가지고 있는 성냥의 개수 K (1 ≤ K ≤ N)이 주어진다.

둘째 줄부터 N개의 줄에는 구사과의 집을 방문하는 친구의 도착 시간 Ti가 i가 증가하는 순서대로 주어진다. (1 ≤ Ti ≤ 1,000,000,000) 동시에 두 명이 방문하는 경우는 없기 때문에, 모든 1 ≤ i ≤ N-1에 대해서 Ti < Ti+1 를 만족한다.

출력

첫째 줄에 난로가 켜져 있는 시간의 최솟값을 출력한다.

난로

접근방법

세번째 예제와 같이 친구 3명이 오고 성냥이 3개 있을때, 처음 친구가 왔을때 난로를 켜는데 하나를 쓰고 나머지 K-1개 (2개)를 다음 친구가 올 때까지 가장 오래 걸리는 시간에 난로를 껏다 켜는데 사용하면 된다.

즉, 성냥 하나로 난방 가능한 전체시간 (prev + 1) - enter_time 에서 먼저 온 친구가 나가고 다음 친구가 들어오는 사이의 간격 N-1개 중에 가장 큰 K-1개의 간격을 고르고 그 간격사이에 난로를 끄면 된다.

구현

#include<iostream>
#include<queue>
#define ll long long
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k, prev, now;
    priority_queue<ll> pq;
    ll ans = 0;
    int enter_time, exit_time;
    enter_time = 0;

    cin>>n>>k>>prev;

    enter_time = prev;

    for(int i=0; i<n-1; i++)
    {
        cin>>now;
        pq.push(now - prev - 1);
        prev = now;
    }
    ans = (prev + 1) - enter_time;

    while(--k)
    {
        ans -= pq.top();
        pq.pop();
    }

    cout<<ans;
    return 0;
}