[백준 17612] 쇼핑몰 (C++)

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

17612번: 쇼핑몰

 

1. 주의할 점

- 우선 순위큐에 사용될 정렬 방법을 잘 정리한다

- 사람수 < 카운터 수 일 때?

 

2. 구현

- Cmp 비교함수를 통해 우선순위큐의 정렬 방법을 정리한다

- Counter의 수만큼 enterCounter 우선순위큐에 미리 삽입한다 (id는 0으로 설정. 이유는 하단에..)

- id와 물건의 수 w를 입력받고, enterCounter의 top에 있는 원소를 Pop하고 현재 들어갈 고객에 대한 정보를 삽입한다 - 이때, 고객의 id를 나타내는 id가 0이 아니라면 goExit 우선순위큐에 삽입한다(나가는 순서)

- goExit 우선순위큐에서 삽입할 때에는 tmp.cidx의 값을 음수로 바꿔서 삽입한다(카운터 번호가 높을수록 먼저 나간다)

- num만큼 입력을 정보를 입력 받은 후, enterCounter에 고객에 대한 정보가 남아있을 수 있으니, enterCounter 우선순위큐에 남은 원소를 위의 조건과 동일하게 처리한다

- goExit 우선순위큐에서 1개씩 뽑으면서 Id*나가는 순번을 Answer에 저장한다. 이때, Int형을 벗어날 수 있으니 Long Long으로 설정한다

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
struct info {
	long long id;
	int cidx, val;
};
struct cmp {
	bool operator()(info &a, info &b) {
		if (a.val == b.val) {
			return a.cidx > b.cidx;		//계산대 번호
		}
		return a.val > b.val;		//끝나는 시간
	}
};
info tmp;
int num, k, w;
long long id;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num >> k;
	priority_queue<info, vector<info>, cmp> enterCounter, goExit;
	long long answer = 0;
	for (int i = 0; i < k; i++)
		enterCounter.push({ 0,i,0 });
	for (int i = 0; i < num; i++) {
		cin >> id >> w;
		tmp = enterCounter.top();
		enterCounter.pop();
		enterCounter.push({ id,tmp.cidx,tmp.val + w });
		if(tmp.id>0)
			goExit.push({ tmp.id,-tmp.cidx,tmp.val });
	}
	while (!enterCounter.empty()) {
		tmp = enterCounter.top();
		enterCounter.pop();
		if(tmp.id > 0)
			goExit.push({ tmp.id,-tmp.cidx,tmp.val });
	}
	int cnt = 1;
	while (!goExit.empty()) {
		long long vv = goExit.top().id;
		goExit.pop();
		answer += (vv*cnt);
		cnt++;
	}
	cout << answer;
	return 0;
}