Compy's Blog
264 words
1 minutes
[BOJ] 컵라면
2025-09-21

컵라면

TimeLimitMemoryLimitConditionTAG
2s256MB1 ≤ N ≤ 200,000Sort, 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;
}



[BOJ] 컵라면
https://compy07.github.io/Blog/posts/boj/1781/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-09-21