백준 1781 컵라면

문제 URL : https://www.acmicpc.net/problem/1781

1781번: 컵라면

문제 접근법 : 

PQ를 사용하는게 핵심입니다.

 

첫번째: 그리디 알고리즘문제이기 때문에 정렬은 핵심입니다. 우선은 데드라인이 지나기전에 그안에서 최대로 받을수있는 컵라면수를 받아야하기에 데드라인기준으로 오름차순 컵라면수 기준으로 내림차순으로 정렬했어요

 

둘째 : minheap을 사용해서 첫번째부터 n번째까지 확인하면서 pq에 담습니다. 집어넣습니다. pq에 집어넣을때마다 사이즈가 증가하는데 이사이즈가 곧 데드라인 시간이라고 생각하시면 문제가 곧바로 풀립니다. 즉 사이즈가 증가할때마다

시간이 증가했다는 뜻이되고 사이즈가 데드라인보다 크다면 pq안에있던것은 그문제를 풀수없다는 뜻이 되버리기 때문에 n까지 돌렸으면 남아있는 컵라면수를 다더하면 그문제만 풀게 됩니다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

//By 콩순이냉장고 #include<iostream> #include<string> #include<algorithm> #include <vector> #include <queue> #include <functional> using namespace std; int n; typedef pair<int, int> p; vector<p> v;   bool cmp(p a, p b){     if (a.first < b.first)         return true;     else if (a.first == b.first&&a.second>b.second)         return true;     return false; }   void input() {     cin >> n;     v.resize(n);     for (int i = 0; i < n; i++)         cin >> v[i].first >> v[i].second; } void solve() {     sort(v.begin(), v.end());     int sum = 0;     priority_queue<int, vector<int>, greater<int>> pq;     sort(v.begin(), v.end(), cmp);     for (int i = 0; i < n; i++)     {         pq.push(v[i].second);         if (pq.size() > v[i].first)//size가 곧 시간이고 사이즈가 더크다는것은 데드라인안에 풀수없는 문제             pq.pop();     }       while (!pq.empty())         sum += pq.top(), pq.pop();     cout << sum << endl; } int main(void) {     ios_base::sync_with_stdio(false);     cin.tie(0);     cout.tie(0);     input();     solve();   }     Colored by Color Scripter

cs

 

 

궁금한점 혹은 모르는점, 혹시 제가 틀린점이 있다면 언제든지 댓글을 이용해주시길 바랍니다.