백준 17612번, 한국정보올림피아드 KOI 2019년 1차 대회 고등부 1번, 쇼핑몰 풀이

문제

백준 17612번

풀이

정해는 우선순위 큐를 사용하는 것이지만 $ N $의 크기가 작기 때문에 단순 구현으로 풀 수 있는 문제입니다.

 

기다리는 고객들을 큐로 관리하고 계산대에 있는 고객들을 벡터로 관리합니다.

계산대에 있는 고객들 중 남은 물건 수의 최솟값을 $ M $이라 두면, 계산대를 순회하면서 모든 고객의 물건을 $ M $개씩 빼서 $ 0 $이 되면 쇼핑몰을 빠져나오는 벡터에($ exit $) 넣어주고 빈 자리에는 기다리는 고객들의 큐에서 하나를 빼서 넣어줍니다.

 

 나오는 순서는 계산대 번호가 큰 순서대로지만, 순회는 작은 숫자부터 했기 때문에 $ exit $을 뒤에서부터 처리해서 답을 구해주면 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ll;
queue<pair<ll, ll>> q;
vector<pair<ll, ll>> l;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);

	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		ll id, w;
		cin >> id >> w;
		q.push({id, w});
	}
    
	l.resize(k);
	for (int i = 0; i < k && !q.empty(); i++) {
		l[i] = q.front();
		q.pop();
	}

	ll exit = 1;
	ll ans = 0;
	while (exit <= n) {
		ll minimum = 20;
		vector<pair<ll, int>> out;
		for (const auto &a : l) if (a.second > 0) minimum = min(a.second, minimum);
        
		for (int i = k - 1; i >= 0; i--) 
            if (l[i].second > 0 && !(l[i].second -= minimum))
                ans += exit++ * l[i].first;
        
		for (int i = 0; i < k; i++) 
            if (!(l[i].second)) {
                l[i].second = -1;
                if (q.empty()) break;
                l[i] = q.front();
			    q.pop();
            }
    }

	cout << ans;
}