[BOJ/백준][Gold1] 17612 : 쇼핑몰 (C++)

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

17612번: 쇼핑몰

 

 

[난이도] Gold1
[유형] 우선순위큐

[풀이]
struct P{
    int id,t,pos;
}
id : id, t : 계산이 끝나는 시간, pos :계산대의 위치
위와 같이 구조체를 정의해줍니다. 그리고
우선순위큐의 comparator 객체를 정의하여
끝나는 시간 t가 작을수록 , 출구에 가까운 계산대 (pos가 클수록)
top에 오도록 해줍니다.

그 뒤 매 루프마다 끝나는 시간이 빠른 모든 원소들을 pop 해준 뒤
ans vector에는 id를 저장해줍니다. 출구쪽부터 pop되기 때문에 이 순서로 ans vector에 저장해주면 됩니다.

rp vector에는 pop되는 순서대로 pos를 저장해줍니다. 이 rp vector를 뒤집은 뒤 반대로 순회하면서
나온 pos에 순차적으로 고객들을 push해줍니다. 시간은 현재 pop된 t+(고객의 물건 수)를 해주면
끝나는 시간을 넣어줄 수 있습니다.

위 과정을 반복하면서 ans vector를 채워주면 정답을 구할 수 있습니다.

 

#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;
int N,k;
pair<int,int> a[1000000];
struct P{
    int id,t,pos;
}; 
struct cmp{
    bool operator()(P& a,P& b){
        if(a.t > b.t) return true;
        else if(a.t == b.t){
            if(a.pos<b.pos) return true;
        }
        return false;
    }
};
int main(){
    scanf("%d%d",&N,&k);
    for(int i=0;i<N;i++) scanf("%d%d",&a[i].first,&a[i].second);
    priority_queue<P,vector<P>,cmp> pq;
    int i=0;
    for(;i<N&&i<k;i++) pq.push({a[i].first,a[i].second,i});
    vector<int> ans;
    for(;i<N;i++){
        auto [id,t,pos] = pq.top();
        vector<int> rp;
        while(!pq.empty() && pq.top().t==t){
            rp.push_back(pq.top().pos);
            ans.push_back(pq.top().id);
            pq.pop();
        }
        reverse(rp.begin(),rp.end());
        for(auto r : rp){
            pq.push({a[i].first,t+a[i].second,r});
            i++;
            if(i>=N) break;
        }
        i--;
    }
    while(!pq.empty()){
        auto [id,t,pos] = pq.top(); pq.pop();
        ans.push_back(id);
    }
    long long total=0;
    for(int i=1;i<=N;i++) total+=i*(long long)ans[i-1];
    printf("%lld",total); 
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/17612.cpp