[그리디 / BOJ 1781 / C++] 컵라면

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

1781번: 컵라면

1) deadline / 컵라면 개수를 벡터에 집어 넣고, 오름차순 정렬을 한다.
2) 벡터를 순회하면서, 처음 요소의 컵라면부터 하나씩 최소힙에 넣어준다.
2-1) 만약, 이때, 힙의 size보다 넣었을때 그 deadline이 크다면, 해당 힙에서 하나씩 꺼낸다. (컵라면이 최대가 되는 경우만 모인다!)

** 이 문제는 이상하게 tie가 통하지 않았다.. 컴파일 에러나면 tie대신 pair를 묶을때는 { }를 쓰자..!

 

이 문제는 처음 접하면 어렵겠지만 

https://die-will-coding.tistory.com/61

[그리디 / BOJ 2109 / C++] 순회강연

 

위 문제를 한번 보고오자!! 그러면 뭐이리 쉬워하면서 풀 것이다!

 

바로 코드를 보자!

 

#include <bits/stdc++.h>

using namespace std;

int N, dl, cups, ret;
vector<pair<int,int>> v;
priority_queue<int, vector<int>, greater<int>> pq; // 최소힙

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        
        cin >> dl >> cups;
        v.push_back({dl, cups});
        
        
    }
    
    sort(v.begin(), v.end());
    
    for(auto i : v){
        pq.push(i.second);
        
        while(pq.size() > i.first){
            pq.pop();
        }
        
    }
    
    while(pq.size()){
        ret += pq.top();
        pq.pop();
    }
    
    cout << ret <<'\n';
    
}

 

태그 : 1780, BOJ, C++, 백준, 재귀, 재귀함수, 종이의 개수