[BOJ 17612 // C++] 쇼핑몰

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 17612번 문제인 쇼핑몰이다.
문제는 아래 링크를 확인하자.

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

17612번: 쇼핑몰

문제에서 주어진 규칙을 잘 읽고 그대로 시뮬레이션을 돌려보자.

 

손님들은 계산을 빨리 마친 순서대로, 시각이 같다면 계산대 번호가 클 수록 먼저 나가므로 이 둘을 비교 기준으로 삼는 우선순위 큐를 만들어 시뮬레이션을 진행할 수 있다.

 

매 시각마다 계산을 마친 손님이 있다면 그 손님들이 모두 쇼핑몰을 먼저 나간 뒤 그 자리에 새로운 손님이 계산을 하러 들어오기 시작해야 하는 점에 유의하자. 즉 손님을 한명 내보내고 그 자리에 바로 새로운 손님을 채워넣는 식의 구현을 하면 안 된다. 항상 번호가 큰 계산대의 손님서부터 나가고 번호가 작은 계산대부터 새 손님을 채워넣으므로 스택과 같은 형태의 자료구조를 이용하면 이를 편하게 구현할 수 있을 것이다.

 

문제 지문에도 적혀있지만 32비트 정수 자료형의 오버플로우에 유의하여 구현하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;

int N, K;
priority_queue<pair<pair<int, int>, int>> pq; // {{-계산마치는시각,계산대번호},회원번호}
vector<int> emptycashier;
int curtime = 0;
ll turn = 1;

ll ans = 0;

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

	cin >> N >> K;
	for (int k = K; k > 0; k--) emptycashier.emplace_back(k);

	while (N--) {
		int id, w; cin >> id >> w;
		if (emptycashier.empty()) {
			curtime = pq.top().first.first;
			while (!pq.empty()) {
				if (pq.top().first.first < curtime) break;
				ans += (turn++) * (ll)pq.top().second;
				emptycashier.emplace_back(pq.top().first.second);
				pq.pop();
			}
		}
		pq.push(make_pair(make_pair(curtime - w, emptycashier.back()), id));
		emptycashier.pop_back();
	}
	while (!pq.empty()) {
		ans += (turn++) * (ll)pq.top().second;
		pq.pop();
	}

	cout << ans;
}