[백준/C++] 17612번 쇼핑몰

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

17612번: 쇼핑몰

 

문제 분석

시뮬레이션 문제처럼 보이기도 하지만, 조금 고민해보면 실시간으로 고객들이 계산대로 이동했다가 출구로 빠져나가는 것이 아니므로 우선순위 큐를 이용하면 문제를 쉽게 해결할 수 있다는 것을 알 수 있습니다. 차근차근 어디서 어떻게 우선순위 큐를 사용해야 할지 생각해봅시다.

 

문제 풀이

우선은 계산대를 우선순위 큐로 만들어야 할 것 같습니다. 이 우선순위 큐의 규칙은 다음과 같습니다.

1. 기다리는 시간이 짧은 계산대일수록 우선순위가 높다
2. 기다리는 시간이 같다면 계산대 번호가 낮을수록 우선순위가 높다

예제를 통해서 이 우선순위 큐가 어떻게 작동하는지 봅시다. 예제에서는 3개의 계산대가 있습니다.

아직 계산대에는 아무도 줄을 서고 있지 않으므로 모든 계산대는 기다리는 시간이 0초입니다. 계산대 번호를 오름차순으로 우선순위 큐가 정렬되어 있습니다.(실제로는 heap으로 구현된 우선순위 큐의 내부가 정렬되어 있지는 않지만 쉬운 이해를 위해 정렬되어 있다고 생각합시다.) 이제 id가 123인 손님이 물건 4개를 가지고 들어옵니다. 가장 우선순위가 높은 계산대인 1번으로 안내됩니다.

1번 계산대의 대기시간이 4초가 되고, 우선순위가 낮아집니다. 다음으로 id가 21인 손님이 물건 5개를 가지고 들어옵니다. 가장 우선순위가 높은 계산대인 2번으로 안내됩니다.

2번 계산대의 대기시간이 5초가 되고, 1번 계산대보다 대기시간이 길기 때문에 우선순위가 1번 계산대보다 낮습니다. 손님이 들어올 때마다 우선순위가 가장 높은 계산대로 안내하고, 그 계산대의 대기시간에 손님이 가져온 물건 개수를 더해주면 모든 손님들을 규칙에 맞게 계산대로 안내할 수 있게 됩니다.

다음 문제는 손님들을 내보내는 순서입니다. 손님들을 내보내는 순서 역시 우선순위 큐를 이용하면 쉽게 알아낼 수 있습니다. 이 우선순위 큐의 규칙은 다음과 같습니다.

1. 계산을 마치는 시간이 빠를수록 우선순위가 높다
2. 계산을 마치는 시간이 같다면, 계산대 번호가 높을수록 우선순위가 높다

손님이 계산대에 줄을 서는 동시에 이 우선순위 큐에 id, 계산대 번호, 대기시간을 enqueue 하면 됩니다. 예제에서 5명의 손님이 들어오는 동안 이 우선순위 큐가 어떻게 작동하는지 순서대로 봅시다.

모든 손님들이 우선순위 큐에 추가되면, 순서대로 손님들을 내보내면 됩니다.

 

코드

#include<iostream>
#include<queue>

using namespace std;

struct checkout
{
    int num;
    int waiting;
};

struct customer
{
    int id;
    int checkout_num;
    int exit_time;
};

struct checkout_cmp
{
    bool operator()(checkout &a, checkout &b)
    {
        if(a.waiting==b.waiting) return a.num>b.num;
        return a.waiting>b.waiting;
    }
};

struct customer_cmp
{
    bool operator()(customer &a, customer&b)
    {
        if(a.exit_time==b.exit_time) return a.checkout_num<b.checkout_num;
        return a.exit_time>b.exit_time;
    }
};

int N, K, id, w, t, c_num, coeff=1;
long long ans;
priority_queue<checkout, vector<checkout>, checkout_cmp> pq_in;
priority_queue<customer, vector<customer>, customer_cmp> pq_out;

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

    cin>>N>>K;

    for(int i=1; i<=K; i++) pq_in.push({i, 0});

    for(int i=0; i<N; i++)
    {
        cin>>id>>w;
        
        t=pq_in.top().waiting+w;
        c_num=pq_in.top().num;

        pq_in.pop();
        pq_in.push({c_num, t});
        pq_out.push({id, c_num, t});
    }

    while(!pq_out.empty())
    {
        ans+=(long long) coeff*pq_out.top().id;
        coeff++;
        pq_out.pop();
    }

    cout<<ans;

    return 0;
}