[BOJ/백준][Gold2] 1781 : 컵라면 (C++)

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

1781번: 컵라면

 

 

[난이도] Gold2
[유형] Greedy

[풀이]
문제들 중에 데드라인이 최대인 문제의 데드라인이 M일 때,
M+1시간부터는 모든 문제의 데드라인이 종료되므로 문제를 풀 수 없습니다.
결국 1,2,3...M 시간에 각각 최대 1문제를 풀 수 있고 각 시간에 컵라면을 최대로 하기에 유리한 문제를 풀어야 합니다.

Greedy 알고리즘을 이용해야 하는데
M,M-1,M-2...1 과 같이 풀어야 하는 문제를 거꾸로 구해주면 쉽게 해결이 가능합니다.

1) 각 문제를 데드라인 순서로 정렬
2) i를 M~1 순서로 순회하면서 i보다 크거나 같은 데드라인을 가진 문제들의 컵라면 수를 우선순위 큐에 push
3) i시간에 풀 수 있는 문제는 과정 2)에 의해 모두 우선순위 큐에 들어있으므로 큐의 top이 결국 i시간에 선택할 수 있는    최적의 문제이므로 컵라면의 수를 ans에 더해줌

위의 과정을 반복하면서 누적된 ans 값이 최종 정답입니다.

 

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int N,M;
pair<int,int> a[200000];
int main(){
    scanf("%d",&N);
    for(int i=0;i<N;i++) {
        scanf("%d%d",&a[i].first,&a[i].second);
        M=max(M,a[i].first);
    }
    int ans=0;
    sort(a,a+N);
    priority_queue<int> pq;
    int j=N-1;
    for(int i=M;i>=1;i--){
        for(;j>=0&&a[j].first>=i;j--) pq.push(a[j].second);
        if(!pq.empty()) {
            ans+=pq.top();
            pq.pop();
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold2/1781.cpp