[baekjoon] 13904

과제

문제

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

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

입력

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

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

출력

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

예제 입력

7
4 60
4 40
1 20
2 50
3 30
4 10
6 5

예제 출력

185

풀이

가능한 많은 점수를 받아야 하기 때문에 그리디를 떠올렸다.

우선 순위 큐에 입력 받은 값을 넣어주고 schedule 이라는 배열을 만들어 k번째 날에 진행할 과제가 있는지를 기록했다.

 

1. 우선 순위 큐에 입력 받기 pair<점수, 마감일>
2. 큐에서 하나 선택, 큐가 빌 때까지
3. 선택한 과제의 schedule[마감일] 이 비어있으면 schedule[마감일]에 진행.
4. 그렇지 않으면 마감일에서 하루씩 앞으로 미루면서 가능한 날 탐색
5. 2~4번 과정 반복

#include <iostream>
#include <queue>

using namespace std;

priority_queue<pair<int, int>> q;   //score deadline
int n;
int schedule[1000];
int findindex(int day){
    int index = day;

    while(schedule[index] != 0 && index != 0)index--;
    return index;
}

long long solve(){
    long long sum = 0;
    while(!q.empty()){
        int score = q.top().first;
        int day = q.top().second;
        q.pop();

        //search index;
        int index = schedule[day] == 0 ? day : findindex(day);

        if(index == 0)continue;
        else{
            schedule[index] = 1;
            sum += score;
        }
    }
    return sum;
}

void input(){
    cin >> n;
    int score, day;
    for(int i = 0; i < n; i++){
        cin >> day >> score;
        q.push({score, day});
    }
}

int main(){
    input();
    cout << solve();
}