[BOJ] 백준 17612. 쇼핑몰 (Gold I)

2019 KOI 1차대회 고등부 1번 문제이다.

1차대회답게 문제가 크게 어렵진 않았다. (라고 하기엔 대학생되기 전까지 KOI 존재를 전혀 몰랐던 내가 할 말은 아닌 것 같다)

문제는 아래와 같다.

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

17612번: 쇼핑몰

---

의식의 흐름 및 해설

우선순위가 정해져 있고, 대기열을 이용하는 문제이기 때문에 우선순위큐를 사용해야 함을 한눈에 파악할 수 있다.

처음에는 대기열이 K개이기 때문에 우선순위큐를 만들고 큐를 여러개 만들까 생각을 했는데, 

우선순위큐에 담을 정보를 id, w 말고도 몇 번째 계산대(이하 n번째 계산대)에 있을지 담아주면 좋을 듯하다는 생각이 들었다. 우선순위 큐의 cmp 조건은 w가 작은 순으로, w가 같다면 n이 큰 순으로 우선순위를 정해주었다.

 

그런데 예제 답이 13900이 아닌 13942가 나와서 다시 문제를 살펴보니,

비록 계산을 마친 손님은 n이 큰 순으로 빠져나가지만, 

계산을 하려는 손님은 n이 작은 순으로 들어온다는 것이었다.

이는 w가 같을 때, n이 커서 먼저 나간 손님의 계산대로 들어오는 것이 아닌, n이 작아 나중에 나간 손님의 계산대로 먼저 들어간다는 LIFO의 성질을 띄는 것이므로 스택을 추가로 이용해주었다.

vector가 stack의 성질을 가지므로 vector<int> out; 을 추가로 만들어주어 w가 같을 경우는 out 벡터에 담아둔 후, out 벡터에 담긴 사람 수만큼 계산대로 보내주도록 하였다.

---

코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
const int MAX = 100011;
const double INF = 0x3f3f3f3f;
const int LNF = 1e18;
const int MOD = 1e9 + 7;
int N, K;
vector<pi> v;
struct Person {
	int id, w, n;
};
struct cmp {
	bool operator()(Person p1, Person p2) {
		if (p1.w == p2.w)
			return p1.n < p2.n;
		return p1.w > p2.w;
	}
};
priority_queue<Person, vector<Person>, cmp> pq;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> K;
	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		int id, w;
		cin >> id >> w;
		v.push_back({ id, w });
		if (i <= K)
			pq.push({id, w, i});
	}
	int cnt = 0, idx = K;
	vector<Person> out;;
	while(!pq.empty()) {
		while (1) {
			int id = pq.top().id;
			int w = pq.top().w;
			int n = pq.top().n;
			pq.pop();
			ans += 1LL * id * (++cnt);
			out.push_back({ id, w, n });
			if (pq.empty() || pq.top().w != w)
				break;
		}
		for (int i = out.size()-1; i >=0;i--) {
			if (pq.size() < K && idx < N) {
				pq.push({ v[idx].first, v[idx].second + out[i].w,
					out[i].n });
				idx++;
			}
			else
				break;
		}
	}
	cout << ans << "\n";
}

---

꽤나 구현할 게 있어 조금은 까다롭지 않나 생각되는 문제였다.

기하학 문제로 맞왜틀을 겪다가 이 문제를 다행히 한번에 맞춰 힐링됐던 문제.