[백준][그리디] 1781 컵라면 c++구현

목차

 

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

문제

 

문제 구현 방향

우선순위 큐를 이용해 데드라인 별로 정렬한 뒤 순차적으로 넣고 빼는 이해하면 쉬운 문제였다.

생각해내는 것이 많이 어려웠다.

 

 

문제 풀이

위의 예제로 설명하면 다음과 같다.

 

데드라인: 1

1의 컵라면 모두를 큐에 넣는다.

6 7 -> 최대 개수는 1 따라서 6을 빼낸다.

 

데드라인: 2

2의 컵라면 모두를 큐에 넣는다.

7 4 5 -> 최대 개수는 2 따라서 4를 빼낸다.

 

데드라인: 3

3의 컵라면 모두를 큐에 넣는다.

7 5 2 1 -> 최대 개수는 3 따라서 1을 빼낸다.

 

데드라인: 6

6의 컵라면 모두를 큐에 넣는다.

7 5 2 1 - > 최대 개수는 6 따라서 빼지 않아도 된다.

 

답 -> 7 5 2 1

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>

using namespace std;
typedef long long ll;
ll N;

priority_queue<ll,vector<ll>, greater<ll>> q;
vector<ll> v[200001];
ll sum = 0;
ll limit = 0;
ll dead = 0;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;

    ll time, cnt;
    for (int i = 0; i < N; i++) {
        cin >> time >> cnt;
        v[time].push_back(cnt);
        dead = max(dead, time);
    }

    for (int i = 1; i <= dead; i++) {
        int limit = i;
        for (auto k : v[i]) {
            q.push(k);
        }
        while (q.size() > limit) {
            q.pop();
        }
    }
    while (q.size()) {
  
        sum += q.top();
        q.pop();
    }
    cout << sum;

}