백준 BOJ 17612 - 쇼핑몰

우선순위 큐 문제

매워요 ㅠㅠ

 

일단 당장 보고 생각난건 우선순위 큐와 위상정렬이다.

근데 다시 :thinking: 과정을 한번 거쳐보고 위상정렬처럼 얘가 정확히 여기 들어간다는

보장이 없어서

우선순위큐로 풀었다.

 

struct people에는 계산시간, 회원번호, 계산대번호 세가지를 저장하고

 

cmp_pq는 pq를 정렬하기 위한 비교함수,

cmp_v  는 벡터를 정렬하기위한 비교함수이다.

 

pq에다 카트를 넣음으로써 계산대가 다 찬 뒤

다음으로 나올 카트를 고를때 pq.top()으로 꺼낼 수 있게 했고,

계산을 마칠때 나오는 순서가 우선 시간순,

시간이 같을때는 안내되는 순서 = 계산대번호가 작은순으로 pq에 넣어서 뽑아주고,

pq에 계산대의 갯수만큼의 사람이 들어간 경우 모두 계산중인 상황이므로

pq에서 한명을 뽑아낸 다음, 그사람의 계산까지 걸린 시간을 벡터에 푸시해줬다.

 

이렇게 하면 이제 결과적으로 벡터에는

모든 손님들이

계산을 끝내고 나올때까지 걸린 시간과,

각자의 번호,

각자가 받은 계산대번호 이 세개가 있는데,

우선 시간순 정렬을 하고,

시간이 같을때는 계산대번호가 더 큰 순서대로 정렬을 해준다.

이러면 정렬된 순서가 문제에서 원하는

쇼핑몰을 빠져나오는 순서

와 같아지므로

 

포문돌리면서 계산해주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

struct people{
	int time; // 계산시간
	int num;  // 회원번호
	int cash; // 계산대번호 
};

struct cmp_pq{
	bool operator()(people a, people b){
		if(a.time == b.time) return a.cash>b.cash;
		else                 return a.time>b.time;
	}
};

bool cmp_v(people a, people b){
	if(a.time == b.time) return a.cash>b.cash;
	else                 return a.time<b.time;
}

ll ans;
priority_queue<people, vector<people>, cmp_pq> pq;
vector<people> v;

int main(){
	int n,k;
	int a,b;
	people tmp;
	scanf("%d %d", &n, &k);
	
	int ptr = 0;
	for(ptr; ptr<min(n,k); ptr++){
		scanf("%d %d", &a, &b);
		pq.push({b,a,ptr});
	}
	for(ptr; ptr<n; ptr++){
		tmp = pq.top();
		v.push_back(tmp);
		pq.pop();
		scanf("%d %d", &a, &b);
		pq.push({tmp.time+b, a, tmp.cash});
	}
	
	while(!pq.empty()){ v.push_back(pq.top()); pq.pop(); }
	sort(v.begin(), v.end(), cmp_v);
	for(int i=0; i<v.size(); i++){ ans += (ll)v[i].num * (i+1); }
	
	printf("%lld", ans);
	return 0;
}

깔끔하게 AC컷.