[그리디] BOJ 13904 과제

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

13904번: 과제

 

문제 해결 알고리즘 

 

알고리즘은 간단한데 그걸 구현해내는 아이디를 내기가 좀 어려웠던 문제..

 

1. 점수가 높은 순서대로 (만약에 같으면 일수가 낮은 순서대로) 우선순위 큐에 정렬을 해준다.

 

2. 그 정렬된 큐 값에 일수를 고려한 최대값을 구해준다.

 

1번은 쉽지만 2번에서 막혔다.

배열을 이용해서 문제를 풀 수 있었는데 큐에서 나온 값의 일수부터 1까지의 인덱스 중 차례대로 0이면 거기에 값을 그대로 입력해주고 break를 해준다. 이 방식대로 구현해준다면 배열에 과제의 순서들은 최대값의 순서로 맞춰져 있다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

struct cmp{
    bool operator()(pair<int, int> a, pair<int, int> b){
        if(a.second != b.second) return a.second < b.second; // 점수가 높은 과제 순서대로
        else a.first > b.first; // 점수가 같다면 일수가 적은 것부터 앞으로
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
vector<int> v(1001);

int main(){
    int N; cin >> N;
    int result = 0;

    // pq에 과제들 담기
    for(int i=0;i<N;i++){
        int d, w; cin >> d >> w;
        pq.emplace(d, w);
    }

    while(!pq.empty()){
        
        int num = pq.top().second;
        int day = pq.top().first;

        for(int i=day;i>=1;i--){
            if(v[i] == 0) {
                v[i] = num; break;
            }
        }

        pq.pop();
    }

    for(int i=1;i<=1000;i++){
        result += v[i];
    }

    cout << result;
}