[Greedy] BOJ 1781 컵라면

문제 링크 : www.acmicpc.net/problem/1781

1781번: 컵라면

그리디 알고리즘으로 해결이 가능한 활동 선택 문제이다.

핵심은 각 문제들을 어떤 기준으로 정렬할 것인지(즉, 어떤 문제의 우선순위를 높게 잡을 것인지)이다.

 

① 우선 당연히 받을 수 있는 컵라면의 갯수가 많은 문제를 우선적으로 풀어야 할 것이다.

그림에서 삼각형 안의 숫자가 문제의 보상, 삼각형의 위치가 데드라인이다.

하지만 위와 같은 상황에서, 보상이 8개인 문제를 먼저 풀게 된다면 데드라인이 1인 문제 하나를 풀 수 없게 된다.

보상이 8인 문제는 데드라인이 3이기 때문에 1일까지는 데드라인이 1인 문제를 푸는 것이 더 이득이다.

 

② 그렇다면 보상이 높은 문제들 중 데드라인이 더 빠른 문제를 먼저 풀어야 하나?

하지만 위와 같은 경우에는 데드라인이 1, 2 인 문제를 건너뛰고 데드라인이 3인 문제만을 푸는 것이 이득이다.

결국 보상이 높은 문제를 먼저 푸는 것은 자명하지만, 보상이 높은 문제를 데드라인에 최대한 가깝게 푸는 것이 최대이익을 얻는 방법임을 알 수 있다.

 

따라서 우리는 문제들을 데드라인이 높은 순서대로 확인해야 한다. n일차에 데드라인이 n인 문제를 풀기 전에, 데드라인이 n+1 이상인 문제들을 풀었을 때 더 이득인지 알고 있어야 하기 때문이다.

단, n일차에 풀 수 있는 문제들 중 가장 보상이 높은 문제를 풀어야 한다.

이를 구현하기 위해서는 우선순위 큐를 이용해 최대 데드라인부터 1일씩 내려오며 풀 수 있는 문제들 중 가장 보상이 높은 문제 하나를 뽑아서 풀도록 한다.

현재 보고 있는 데드라인이 감소하여 풀 수 없는 문제가 발생하면, 큐에서 pop한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <memory.h>
#include <algorithm>
#include <string>
 
using namespace std;
typedef pair<int, int> p;
 
int n, max_dead;
vector<p> probs;
 
long long greedy() {
    long long answer = 0;
    int dead = max_dead;
    int prob_idx = 0;
    priority_queue<p> pque;
 
    while (dead > 0) {
        while (!pque.empty() && pque.top().second < dead) pque.pop();
        while (prob_idx < probs.size() && probs[prob_idx].second == dead) {
            pque.push(probs[prob_idx++]);
        }
        if (pque.empty()) {
            dead--;
            continue;
        }
        answer += pque.top().first;
        pque.pop();
        dead--;
    }
    return answer;
}
 
bool cmp(p a, p b) {
    return a.second > b.second;
}
 
void init() {
    int d, r;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d >> r;
        max_dead = max(max_dead, d);
        probs.push_back({ r, d });
    }
 
    sort(probs.begin(), probs.end(), cmp);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
 
    long long answer = greedy();
    printf("%lld\n", answer);
 
    return 0;
}