쇼핑몰( BOJ 17612 )

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

17612번: 쇼핑몰

 

문제 파악하기

N명의 고객이 K개의 계산대에서 계산을 마치고 나가는 순서를 구하는 문제입니다. N명의 고객을 모든 계산대 뒤에 배치하기보다는 1줄로 기다리다가 비어있는 계산대에 배치한다고 생각하면 문제를 단순화시킬 수 있습니다. K개의 계산대 중 가장 먼저 계산이 끝나는 계산대를 구하는 효율적인 방법으로는 우선순위 큐를 사용할 수 있습니다. 우선순위 큐를 사용해 가장 먼저 계산이 끝나는 계산대를 구하고, 나가는 고객을 구한 다음에 다음 고객을 배치시키는 작업을 거치면 문제를 해결할 수 있습니다.

 

문제 해결하기

우선 우선순위 큐를 사용하기 위해서는 어떤 자료구조를 사용해 어떤 순서로 우선순위를 정할지 생각해야 합니다. 우리에게 필요한 정보는 총 3가지 입니다. 고객의 회원번호와 물품 수, 그리고 계산대의 번호입니다. 고객의 회원번호는 우리가 실제로 계산해야할 값이며, 물품 수는 계산할 때 걸리는 시간이며, 물품을 기준으로 우선순위가 결정됩니다. 그리고 계산대 번호는 나중에 나가는 순서를 정하는 값이며, 계산이 끝나는 시간이 동일할 경우 우선순위를 정해주는 값입니다. 이렇게 3가지 정보를 한번에 저장한 다음에 계산이 빨리 끝나는 순서대로 회원번호를 곱해주고, 새로운 고객을 비어있는 계산대에 넣어주면 우리가 원하는 결괏값을 얻을 수 있습니다.

 

다만, 동시에 끝나는 계산대에 대해서는 특별한 처리가 필요합니다. 동시에 끝날 때에는 우선 계산대 번호가 큰 고객부터 밖으로 내보냅니다.  그리고 새로운 고객을 채워넣을 때에는 계산대 번호가 작은 순서대로 넣어주어야 합니다. 이 과정만 추가하면 별다른 문제는 업습니다,.

 

소스코드

#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
#define PAIR pair<int, int>
using namespace std;
 
struct Shop {
    long long int id, w;
    long long int ki;
};
 
int N, K;
int id, w;
vector< PAIR > inp;
 
int idx, cnt;
long long int t, ret;
vector< Shop > v;
 
struct cmp {
    bool operator()(Shop a, Shop b) {
        if(a.w == b.w) return a.ki < b.ki;
        else return a.w > b.w;
    }
};
priority_queue< Shop, vector< Shop >, cmp > pq;
 
int main() {
    scanf("%d %d", &N, &K);
    for(int i=1;i<=N;i++) {
        scanf("%d %d", & id, &w);
        inp.push_back({id, w});
 
        if(i<=K) pq.push({id, w, i});
    }
 
    idx = K;
    while(cnt<N) {
        // 초기화
        v.clear();
        t = pq.top().w;
 
        // 동시에 나가는 경우 한번에 처리하기
        while(!pq.empty() and pq.top().w == t) {
            v.push_back(pq.top());
            pq.pop();
        }
 
        // 동시에 나갈 경우, 뒷 번호 계산대부터 나감
        for(int i=0;i<v.size();i++) {
            cnt++;
            ret += v[i].id*cnt;
        }
 
        // 동시에 들어갈 경우, 앞 번호 계산대부터 들어감
        for(int i=v.size()-1;i>=0 and idx<N;i--,idx++) {
            pq.push({inp[idx].first, inp[idx].second+t, v[i].ki});
        }
 
    }
 
    printf("%lld", ret);
}

후기

전형적인 우선순위 큐를 활용하는 문제입니다. 계산이 동시에 끝나는 경우를 처리하는데 살짝 어려움이 있지만 전체적으로 알고리즘을 설계하는데 난이도가 높지는 않았습니다. 우선순위 큐를 활용하는 괜찮은 문제라고 생각이 듭니다.