백준 g2 1781 컵라면 c++

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

1781번: 컵라면

문제

N개의 문제가 주어지고, 각 문제의 dead line과 맞혔을 때 주어지는 컵라면 개수가 주어진다. 

 

예시) 문제 번호/ 데드라인 / 컵라면 수

1	2	3	4	5	6	7
1	1	3	3	2	2	6
6	7	2	1	4	5	1

동호가 먹을 수 있는 최대 컵라면 개수는?

 

풀이

문제를 보자마자 그리디인 건 알았지만 앞에서부터 정렬하는 방식으로는 도저히 방법이 떠오르지 않았다.

결국 답지를 슬쩍 봐서 뒤에서부터 시작해야 한다는 힌트를 얻었다 (https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x17/solutions/1781.cpp).

 

시간의 앞에서부터 시작하는 경우엔 어떤 경우는 컵라면 개수를 많이 주는 게 먼저고, 어떤 경우에는 데드라인이 널널한 걸 뒤로 빼야 최대의 개수를 구할 수 있다. 

 

그러나 뒤에서부터 시작하면서 각각의 날짜에 최대로 컵라면을 주는 문제를 고르면 가능한 최적의 날에 (뒤에서부터 시작하므로 데드라인이 빡빡한 문제를 앞으로 몰아줄 수 있음) 최대의 컵라면 개수를 구할 수 있다.

 

수도 코드

for: time N ~ 1
    1. time이 deadline인 문제들 모두 pq에 push
    2. 컵라면 배치
    	if pq.empty()
        	continue
        else
        	ans += pq.top()
            pq.pop()

 

전체 코드

/*boj g2 1781 컵라면*/
#include <iostream>
#include <queue>
#include <vector>
#define MAXN 200002
using namespace std;

int N;
vector<vector<int>> probs(MAXN);
priority_queue<int> pq;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    int d, c;
    for (int i = 0; i < N; i++) {
        cin >> d >> c;
        probs[d].push_back(c);
    }

    int ans = 0;
    for (int time = N; time >= 1; time--) {
        for (int c : probs[time]) {
            pq.push(c);
        }

        if (pq.empty())
            continue;
        else {
            ans += pq.top();
            pq.pop();
        }
    }

    cout << ans << "\n";
}