[BOJ] 13904 - 과제

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

BOJ - 과제

문제 유형: 그리디, 우선순위 큐, 정렬

문제 난이도: Gold III

시간 제한: 1초

메모리 제한: 256MB

 

문제

웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.

웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.

 

입력

첫 줄에 정수 N (1 ≤ N ≤ 1,000)이 주어진다.

다음 줄부터 N개의 줄에는 각각 두 정수 d (1 ≤ d ≤ 1,000)와 w (1 ≤ w ≤ 100)가 주어진다. d는 과제 마감일까지 남은 일수를 의미하며, w는 과제의 점수를 의미한다.

 

출력

얻을 수 있는 점수의 최댓값을 출력한다.

 

풀이

우선순위 큐에 {마감기한, 점수}를 넣고, 점수에 대해, 그리고 같은 점수에 대해서는 마감기한에 대해 최대 힙으로 만들어 저장한다.

 

가장 늦은 시간부터 해서, 역순으로 현재 수행해서 최고의 점수를 얻을 수 있는 과제를 해야 한다.

time = maxTime부터 해서, 현재 time에서 가능한 가장 큰 점수의 과제를 골라서 수행한다.

 

이렇게 쌓인 누적 점수가 최선이다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

struct comp {
    bool operator()(const pii &a, const pii &b) {
        if (a.second == b.second) {
            return a.first < b.first;
        }
        return a.second < b.second;
    }
};

int main(int argc, char *argv[]) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int maxTime = -1;
    priority_queue<pii, vector<pii>, comp> pq;
    for (int i = 0; i < n; i++) {
        int d, w;
        cin >> d >> w;
        pq.emplace(d, w);
        maxTime = max(d, maxTime);
    }

    int ans = 0;
    for (int time = maxTime; time >= 1; time--) {
        int deadline = -1, weight = -1;
        stack<pii> stk;
        while (!pq.empty()) {
            int d, w;
            d = pq.top().first;
            w = pq.top().second;
            pq.pop();

            if (d >= time) {
                deadline = d;
                weight = w;
                break;
            }

            stk.emplace(d, w);
        }

        while (!stk.empty()) {
            pq.emplace(stk.top().first, stk.top().second);
            stk.pop();
        }

        if (weight != -1) ans += weight;
    }

    cout << ans << "\n";

    return 0;
}