[BOJ] 1781번 : 컵라면

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

1781번: 컵라면

 

priority queue(max heap)과 greedy 문제다.

 

중요한 아이디어는 앞 시간부터 데드라인을 계산하면 고려할 대상이 너무 많아지니 뒷 시간부터 데드라인을 계산하는 것이다. 만약 현재가 시간 t라면, 데드라인이 t보다 큰 모든 문제 중에서 가장 점수가 큰 문제를 골라서 해결하면 된다. 이 경우 시간 t까지 보았을 때 얻을 수 있는 점수 중에서 가장 큰 점수를 얻게 되므로 시간 1이 되었을 때도 optimal solution을 보장하게 된다.

 

이때 데드라인이 t보다 큰 모든 문제 중 가장 점수가 큰 문제를 고르는 과정을 linear하게 수행하면 O(n)이므로 전체 time complexity가 O(n^2)이 되어 문제를 풀 수 없다. 따라서 값의 push와 max값의 pop이 O(lgN)만에 수행되는 priority queue를 사용하겠다는 생각을 하면 된다.

 

다만 STL priority queue를 잘 써보지 않은 탓에 compare 함수를 만드는 방법을 처음 깨달았다.

 

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
 
using namespace std;
 
int n;
vector<pair<int, int>> prob;
 
struct comp2 {
    bool operator()(pair<int,int>a, pair<int,int>b) {
       return a.second<b.second;
    }
};
 
bool comp(pair<int,int> a, pair<int,int> b) {
    return a.first<b.first;
}
 
priority_queue<pair<int,int>, vector<pair<int,int>>, comp2> probAble;
 
int main ( void ) {
    
    int temp1, temp2;
    int maxScore = 0;
    int maxTime = -1, curTime;
    int index, sum=0;
    prob.push_back(make_pair(0,0));
    
    scanf("%d", &n);
    for(int i =0 ; i<n; i++) {
        scanf("%d %d", &temp1, &temp2);
        prob.push_back(make_pair(temp1,temp2));
        maxTime = max(maxTime, temp1);
    }
    
    sort(prob.begin(),prob.end(), comp);
    index = n;
    
    for(curTime = maxTime; curTime > 0; curTime--) {
        while(prob[index].first >= curTime ) {
            probAble.push(prob[index]);
            index--;
        }
        if(probAble.empty()) continue;
        sum+= probAble.top().second;
        probAble.pop();
    }
    
    cout<<sum<<endl;
    return 0;
}

 

이 소스는 내 github에서도 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/1781/1781.cpp

Jordano-Jackson/PS