1781번 컵라면

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

priority_queue를 활용한 Greedy 문제이다.

제일 먼저 정렬을 한다.(데드라인이 제일 중요하므로 우선 그 다음 컵라면의 개수)

알고리즘 진행 동안 데드라인과 priority_queue의 size()를 잘 비교해야한다.

현재 데드라인이 priority_queue의 size()보다 크거나 같으면,('='일 때는 데드라인과 priority_queue의 size()가 같을 수도 있으니)

priority_queue에 마이너스 상태로 넣어준다.(최소 힙으로 만들기 위함 그리고 데드라인보다 작으므로 '더' 진행할 수 있으니 push)

그리고 데드라인이 priority_queue의 size()보다 작으면 priority_queue를 pop() 해줘야 한다.(데드라인을 초과할 수는 없으므로)

pop()을 할 때에는 쓸모없는 것들이 없어진다.

즉, 현재 데드라인을 고려하여 priority_queue 안에는 항상 적절한(정답을 구하기 위한) 컵라면의 개수들이 담겨져 있다.

한 가지로 예를 보자

3

1 2

1 10

3 1

정렬을 하면,

1 2

1 10

3 1

이 된다.

[1, 2]

데드라인 = 1, 컵라면의 개수 = 2, pq.size() = 0

데드라인이 pq.size() 이상이므로, pq.push(-2)를 해준다.

pq의 현재 상태 = [-2](맨 왼 쪽이 꼭대기)

[1, 10]

데드라인 = 1, 컵라면의 개수 = 10, pq.size() = 1

데드라인이 pq.size() 이상이므로, pq.push(-10)를 해준다. → 이 때문에 >=를 해준 것이다. 더 좋은 답을 위한 데이터가 나올 수 있으니.

pq의 현재 상태 = [-2, -10](맨 왼 쪽이 꼭대기)

30번 째 줄에서

데드라인(1) < pq.size()(2) 이므로, pq.pop()을 해줘야 한다. → < 인 이유는 <=로 한다면, pq.size()가 더 작아질 수 있다.

pq의 현재 상태 = [-10](맨 왼 쪽이 꼭대기)

.

.

.

이런 식으로 진행된다.

++)

사실 접근 방법은 결국 "절대로 선택될 수 없는 컵라면"들은 제외하면서 접근해도 된다.

예를 들어

데드라인 컵라면 개수

10 1

10 2

10 3

.

.

앞에 1, 2, 3, .. 개수가 적은 것들은 선택될 수 없다.

그러므로, 우선순위 큐(최소 힙)에 우선 push를 하면서 진행하다가,

해당 i번 째에 대해서 데드라인의 수와 우선순위 큐(최소 힙)의 size()가 같게 만들도록 하면 된다.

(또는 우선순위 큐의 size()가 더 적게)

그러면 위에서 적은 것들부터 데드라인의 개수에 맞게 구할 수 있다.

어차피 정렬하였으므로 데드라인은 증가할 것이고, 최대 데드라인에 맞춰야 하기 때문이다.

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
vector<pair<int, int> > v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\sample_input.txt", "r", stdin);
    cin.tie(0);
    scanf("%d", &n);
    int deadline, cup_count, ans = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &deadline, &cup_count);
        v.push_back({ deadline, cup_count });
    }
 
    sort(v.begin(), v.end());
 
    priority_queue<int> pq;
 
    for (auto i : v) {
        int dl = i.first, cc = i.second;
 
        if (dl >= pq.size()) {
            pq.push(-cc);
        }
 
        while (dl < pq.size())
        {
            pq.pop();
        }
    }
 
    while (!pq.empty())
    {
        ans += -pq.top();
        pq.pop();
    }
 
    printf("%d\n", ans);
 
    return 0;
}

#include <bits/stdc++.h>
 
using namespace std;
 
int n;
priority_queue<int> pq;
vector<pair<int, int> > v;
 
int main()
{
    cin.tie(0);
    scanf("%d", &n);
 
    int deadline, cup;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &deadline, &cup);
        v.push_back({ deadline, cup });
    }
 
    sort(v.begin(), v.end());
 
    for (int i = 0; i < n; i++) {
        int dl = v[i].first, cp = v[i].second;
 
        pq.push(-cp);
        
        while (dl < pq.size())
        {
            pq.pop();
        }
    }
 
    int answer = 0;
 
    while (!pq.empty())
    {
        answer += -pq.top();
        pq.pop();
    }
 
    printf("%d\n", answer);
 
    return 0;
}