[백준 BOJ] 15553 난로

15553_난로

링크

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

 

풀이

 

친구들은 집에 1초씩 있다가 나갑니다.

친구들이 오고 가고 하는 동안 난로를 끄고 켜고 하는 것을 다 고려하긴 좀 힘듭니다.

그렇다면 어떻게 쉽게 풀 수 있을까요?

 

우선 처음 친구가 방문한 시간과 마지막 친구가 나간 시간의 차이를 구합니다.

이 시간은 난로를 친구가 방문했을 때부터 마지막 친구가 나갈 때까지 계속 켜고 있는 상황입니다.

 

그리고 친구가 방문하지 않는 시간(뒤 친구가 방문한 시간 – 앞 친구가 나간 시간)들을 priority queue에 넣고 k-1개만큼 빼줍니다.

성냥으로 다시 난로를 켤 수 있기 때문에 방문하지 않는 시간을 가장 긴 시간부터 절약하는 것이죠. 그러면 답을 구할 수 있습니다.

 

코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

//15553_난로 #include <cstdio> #include <algorithm> #include <queue> using namespace std;   priority_queue<int> pq; int n, k; int t1, t2; int startnum, endnum; int ans;   int main() {     scanf("%d %d", &n, &k);     scanf("%d", &t1);     startnum = t1;       for (int i = 2; i <= n; ++i) {         scanf("%d", &t2);         pq.push(t2 - t1 - 1);         t1 = t2;     }       endnum = t1;     ans = endnum - startnum + 1;       while (--k) {         ans -= pq.top(); pq.pop();     }       printf("%d\n", ans);       return 0; }

cs