264 words
1 minutes
[BOJ] 컵라면
| TimeLimit | MemoryLimit | Condition | TAG | 
|---|---|---|---|
| 2s | 256MB | 1 ≤ N ≤ 200,000 | Sort, Greedy | 
문제는 대놓고 그리디 냄새를 냈지만, 생각보다 간단한 문제임에도 불구하고 오래걸렸다…
간단히 현재 시간까지의 최대값을 유지하면서 진행을 해버리면 됩니다~~
정답 코드
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll = long long;
int N;
pair<int, int> problems[200'001];
int visited[200'001];
bool compare(const std::pair<int, int>& a, const std::pair<int, int>& b) {
    return a.second < b.second;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    
    for(int i = 0; i < N; i++){
        cin >> problems[i].second >> problems[i].first;
//        q.push({problems[i].second, problems[i].first});
//        visited[i+1] = -1;
    }
    sort(problems, problems+N, compare);
    
    
    q.push(problems[0]);
    for(int i = 1; i < N; i++){
        auto [cost, current] = problems[i];
        
        if(current > q.size()){
            q.push(problems[i]);
//            cout <<"size: " << q.size() << " " << current << "\n";
        }
        else{
//            cout << "cost: " << cost << " " << q.top().first << "\n";
            if(cost <= q.top().first) continue;
//            cout << "cost: " << cost << " " << q.top().first << "\n";
            q.pop();
            q.push({problems[i]});
        }
        
//        cout << i << "\n";
    }
    
    
    int result = 0;
    while(!q.empty()){
//        cout << q.top().first << " " << q.top().second << "\n";
        result += q.top().first; q.pop();
        
    }
    
    cout << result;
    return 0;
}

