[백준] 13904번 과제

13904 과제

문제

---

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

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

입력

---

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

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

출력

---

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

---

풀이)

greedy 문제이다. 생각한 과정은 이러하다.

가장 많은 점수를 받고 싶은 것이니깐, 높은 점수를 주는 과제를 먼저 끝낸다.

따라서, 모든 과제의 점수와 남은 일수를 받아와서 

높은 점수순으로 나열하고 / 점수가 같다면 마감일이 남은 일수가 적은 순으로 우선순위를 정한 뒤

우선순위가 높은 과제부터 먼저 한다.

코드를 보면 이해가 더욱 쉬울 것이다.

코드)

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
int n;
vector <pair<int,int>> vec;
int result;
bool visited[1001];
int limit;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int d, w;
        scanf("%d %d", &d, &w);
        limit = max(d, limit);
        vec.push_back({ -w,d }); 
    }
    //점수를 기준으로 내림차순, 점수가 같다면 마감일 오름차순
    sort(vec.begin(), vec.end());
    
    for (int i = limit; i > 0; i--) {
        for (int j = 0; j < vec.size(); j++) {
            // 아직 해당 과제를 수행하지 않았고, 
            //과제의 마감일이 현재 날짜 안에 속한다면
            if (!visited[j] && vec[j].second >= i) {
                result -= vec[j].first;
                visited[j] = true;
                break;
            }
        }
    }
    printf("%d", result);
    return 0;
}

결과)