[백준 19580] 마스크가 필요해

이 문제를 풀고, 그리디를 좀 더 연습해야겠다는 생각이 들었다.

1. 풀이

먼저 나는 정렬 + set으로 풀었지만, 다른 분들의 우선순위 큐 + 정렬 풀이가 좋아, 이 풀이 기준으로 설명한다. 물론 둘다 아이디어는 같고, 구현의 차이이다.

이 문제를 보면 생각보다 고려해야 되는 값이 많아 난감하였다. 하지만 그리디한 아이디어는 금방 찾을 수 있다. 상인들의 마스크 개수에서 딱히 관찰할 수 있는 점은 없고, 각 사람들에게 적당한 순서로 판매를 해야된다는 생각을 할 수 있다.

여기서 어떻게 그리디하게 순서를 정할까? 이 아이디어는 생각보다 금방 찾을 수 있다. 소비할 수 있는 금액의 범위가 작은 사람들부터 판매를 하면 된다. 왜냐하면 선택지가 좁은 사람들부터 판매 하는 것이 더 많이 선택을 할 수 있다.

이 아이디어를 가지고 구현을 하면 된다. 나는 구현에서 많이 막혔다.

2.소스 코드

#include <bits/stdc++.h>


using namespace std;


typedef long long ll;
typedef pair<ll, ll> pi;


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);


    int n, m; cin >> n >> m;
    vector<pi> A(n), B(m);
    for (int i = 0; i < n; i++) cin >> A[i].second >> A[i].first;
    for (int i = 0; i < m; i++) cin >> B[i].first >> B[i].second;
    sort(A.begin(), A.end(), greater<pi>());
    sort(B.begin(), B.end(), greater<pi>());


    priority_queue<ll> pq;
    int pivot = 0;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        while (pivot < n && A[pivot].first >= B[i].first) pq.push(A[pivot++].second);
        while (!pq.empty() && pq.top() > B[i].first) pq.pop();
        while (!pq.empty() && B[i].second--) pq.pop(), ans++;
    }


    cout << ans;


    return 0;
}