BOJ 13904 - 과제

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

13904번: 과제

본 문제의 핵심은, pq를 사용해서 데드라인안에 최대한 점수를 많이 얻는 것을 목표로 해야합니다.

예를 들어, 

4
1 1000
1 100
1 100
1 100

와 같은 데이터가 있다면, $w=1,000$인 과제를 선택하는 것이 최적해입니다.

 

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

예제의 메모에선, 데드라인이 빠른걸(낮은 것) 굳이 안해도 나중의 것을 선택했을 때 더 많은 $w$를 얻을 수 있음을 보여줍니다. 

 

먼저, 데드라인이 빠른 것을 기준으로 과제들을 정렬합니다. ($O(NlogN)$) (데드라인이 짧은것을 먼저 선택하고, 추후에 버리는 선택을 해도 됩니다.)

 

모든 $i$에 대해, pq에 $w_i$를 넣고, (이 pq는 오름차순으로 정렬됩니다.) $ans$에 $w_i$를 더합니다. (과제를 수행)

만약, 과제를 수행하고 난 후의 $day > d_i$ 조건을 만족하면, 수행한 과제 안에 같은 $d_i$가 존재하며, 이는 $d_i \leq day$인 과제를 모두 다 수행할 수 없음을 의미합니다. 따라서 이때 과제중 $w_i$가 가장 낮은 과제를 버리면, (이 $w_i$를 $a$라고 하면,) $w_i>a$인 과제를 수행함으로써 점수를 더 얻을 수 있습니다.

 

vector<pair<int, int> > v;

bool cmp(pair<int, int> &a, pair<int, int> &b) {
    return a.first < b.first;
}

priority_queue<int, vector<int>, greater<int> > pq;

int main() {
    fastio();
    int N;
    cin >> N;
    for(int i=0; i<N; i++) {
        int X, Y;
        cin >> X >> Y;
        v.push_back({X, Y});
    }
    sort(all(v), cmp);
    int ans = 0;
    int day = 0;
    for(int i=0; i<N; i++) {
        pq.push(v[i].second);
        ans += v[i].second;
        day++;
        if(v[i].first < day) {
            day--;
            ans -= pq.top(); pq.pop();
        } 
    }
    cout << ans;
}