[백준 19580번] [그리디/ 우선순위 큐] 마스크가 필요해

문제를 보고 생각보다는 쉽게 그리디 문제임을 파악할 수 있다.

 

문제 조건을 잘 보면, 최대한 많은 시민이 마스크를 구매할 수 있도록 유도해야한다. 즉 상식적으로 이 워딩을 보면 모든 시민들이 구매할 수 있게끔 최적(?)의 방법으로 구매하는 것이 가장 이득이라는 것을 간파할 수 있다.

즉, 이 지점에서 그리디 문제가 아닐까 의심을 해볼 수 있다.

 

직관적으로 잘 생각해보면 마스크를 제일 많이 팔 수 있는 경우는 해당 마스크 가격에만 구매할 수 있는 사람을 최우선적으로 구매권을 주면 된다는 것을 간파할 수 있다.

 

즉, 이 문제를 풀기 위해서는 각 상점을 기준으로 해당 가격 마스크를 시민들의 구매할 수 있는지 여부를 체크하고 그 중 가장 최적의 케이스 순서대로 구매를 진행해야 한다.

 

다만, 이 문제에서 입력값이 매우 큰 상황이므로 전체 탐색을 실행하게 되면 O(N^2)으로 시간 초과가 나게 된다.

(대충 이쯤되면 O(NlgN) 느낌이 오기는 해야한다.)

따라서 오름차순으로 정렬을 하고 순차적으로 살펴주면 된다. 정렬을 해야 마스크를 살 수 있는지 여부를 쉽게 체크할 수 있게 된다. 회의실 배정 문제와 달리 정렬이 들어간 이유에 대해서 잘 이해해야 한다.(정렬이 O(NlgN)이므로 충분하다.)

정렬이 되어 있는 상태이기에, 해당 마스크를 구매할 수 있는지를 전부 체크해주고 구매할 수 있다면 지불 최대치의 한도가 작은 순으로 골라주면 된다.

 

이 지점에서 적은 순으로 픽을 하는 상황이므로 우선순위큐 자료구조를 활용할 수 있다.

 

앞에서부터 순차적으로 처리하면, 무조건 남는 시민들을 끝나는 지점이 작을수록 최적의 케이스를 만족하는 것은 타당하다.

즉 부분 최적구조를 만족하고 있는 상황이므로 그리디 문제로 해결할 수 있게 된다.

 

중요한 지점은 우선순위 큐에 있는 것을 restore 해줄 필요가 없다.

애초에 구매 가능 가격은 낮은 가격 순으로 정렬되어있으므로, pq안에 들어가 있는 것의 하한선이 마스크 가격을 넘지 못한다는 것은 확실하다. 따라서 상한선ㅇ니 마스크 가격을 넘는지 여부만 체크해주면 된다.

 

즉, 우선순위 큐는 정확히 1번만 들어가면 되는 상황이므로 O(nlgn)이면 충분하다.

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
ll N, M;

struct compare{
    bool operator()(pll &temp1, pll &temp2){
        return temp1.second > temp2.second;
    }
};

int main(void){
    fastio;
    cin >> N >> M;
    vector<pll> civil;
    vector<pll> market;
    for(int i = 0; i < N; i++){
        ll temp1, temp2;
        cin >> temp1 >> temp2;
        civil.push_back(make_pair(temp1, temp2));
    }
    for(int i = 0; i < M; i++){
        ll temp1, temp2;
        cin >> temp1 >> temp2;
        market.push_back(make_pair(temp1, temp2));
    }

    sort(civil.begin(), civil.end());
    sort(market.begin(), market.end());

    priority_queue<pll, vector<pll>, compare> pq;

    int current_pos = 0;
    int print_num = 0;

    for(int i = 0; i < M; i++){
        while(current_pos < N && civil[current_pos].first <= market[i].first){
            if(civil[current_pos].second >= market[i].first){
                pq.push(civil[current_pos]);
                current_pos++;
            }
            else current_pos++;
        }
        while(!pq.empty() && market[i].second != 0){
            pll check_value = pq.top();
            pq.pop();
            if(check_value.first <= market[i].first && check_value.second >= market[i].first){
                market[i].second -= 1;
                print_num++;
            }
        }
    }
    cout << print_num << "\n";
    return 0;
}