백준 1781번 컵라면 - C++ 풀이 + 그림 설명

---

 

1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다.

 

1. 시간 역순으로 매일 가능한 문제 중 가장 컵라면을 많이 받을 수 있는 문제를 푼다.

 day일에 풀 수 있는 문제는 데드라인이 day 이상인 문제들이다.

 따라서 N일에 풀 수 있는 문제는 데드라인이 N인 문제들 밖에 없으므로, 그 중에서 가장 컵라면을 많이 주는 문제를 골라야 한다. (N-1)일에는 데드라인이 (N-1)일이거나 N일인 문제들을 풀 수 있다. 데드라인이 N일인 문제 중 가장 많은 컵라면을 주는 문제는 N일에 풀어야 하기 때문에, 이제 그 문제를 제외한 문제들 중에서 가장 많은 컵라면을 주는 문제를 고르면 된다.

 같은 방식으로 N-2, N-3, ..., 1일까지 계속해서 가능한 문제 중 가장 많은 컵라면을 얻을 수 있는 문제를 그리디하게 선택해나가면 된다. 과정을 그림으로 나타내면 아래와 같다.

 

반응형

---

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 200001;

int N;
vector<int> problems[MAX];

int optimize() {
    int ret = 0;
    priority_queue<int, vector<int>, less<int>> pq;
    
    // 시간 역순으로 가장 많은 컵라면을 받을 수 있는 문제를 고른다.
    for (int day=N; day>=1; day--) {
        for (auto p: problems[day]) pq.push(p);
        if (!pq.empty()) {
            ret += pq.top(); pq.pop();
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for (int i=0; i<N; i++) {
        int deadLine, ramen;
        cin >> deadLine >> ramen;
        
        problems[deadLine].push_back(ramen);
    }
    
    cout << optimize();

    return 0;
}