[C++] 백준 17612번: 쇼핑몰

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

17612번: 쇼핑몰

 

 > 접근

아래와 같이 시간을 계속해서 누적시키면서 가장 시간이 적은 것들을 replace하는 방식으로 고민해보았다.

이 때 카운터에서 최소값을 계속해서 찾아야하므로 우선순위큐를 써야한다. 시간 중요하므로 time, id, index 순으로 tuple을 배치한다.

 

나는 입력값을 받으면서 같이 처리하는 식으로 설계하였는데, 방식은 대강 다음과 같다.

toInsert라는 또 다른 우선순위큐를 사용한다. 이곳은 counter를 참조하여 가장 적은 시간들을 모아두는 곳이며, counter과는 달리 tuple의 배치가 index, time, id 순이다. toInsert는 같은 시간인 것들 중에 가장 왼쪽에 위치한 것을 참조하여 그곳을 입력값으로 대체하게끔 설계하였기 때문이다.

 

 > 풀이

상세한 설명은 주석에 달아놓았으니 이를 참고하자.

주의해야할 점은, 출력값인 sum을 갱신해줄 때 나가는 순서가 1, 2, 3, 4, ... 처럼 순차적이지 않다는 것이다. toInsert는 대체할 고객을 고르는 것에 중점을 두고 설계된 우선순위큐이지만, 나갈 때는 들어올 때와는 정반대로, 가장 오른쪽에 있는 고객부터 나가기 때문이다. 이에 대한 변수는 'p'이다.

#include <bits/stdc++.h>
using namespace std;

int N, k;
// time, id, index
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> counter;

// counter에서 가장 낮은 시간인 것들을 time, id, index -> index, time, id로 재배열하여 반환
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> popCounter() {
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> res;
	int time = get<0>(counter.top());
	res.push({ get<2>(counter.top()), get<0>(counter.top()), get<1>(counter.top()) });
	counter.pop();

	while (!counter.empty() && time == get<0>(counter.top())) {
		res.push({ get<2>(counter.top()), get<0>(counter.top()), get<1>(counter.top()) });
		counter.pop();
	}

	return res;
}

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

	cin >> N >> k;

	int i;
	for (i = 0; i < k; i++) {
		counter.push({ 0, 0, i });
	}

	long long sum = 0;
	int p;
	int id, w;

	// index, time, id
	priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> toInsert;
	
	for (i = 0; i < N; i++) {
		cin >> id >> w;

		if (toInsert.empty()) {
			toInsert = popCounter(); // counter -> toInsert
			p = i - (k - 1);
		}

		// 가장 왼쪽에 있는 테이블을 꺼냄
		tuple<int, int, int> top = toInsert.top();
		toInsert.pop();

		// 좌항: 나가는 순서, 우항: id
		sum += (p + toInsert.size()) * get<2>(top);

		// 시간을 계속해서 누적합하는 방식으로 입력 값을 counter에 채워넣음
		counter.push({ get<1>(top) + w, id, get<0>(top) });
	}

	// 남아있는 고객 처리
	for (; i < N+k;i++) {
		if (toInsert.empty()) {
			toInsert = popCounter();
			p = i - (k - 1);
		}

		tuple<int, int, int> top = toInsert.top();
		toInsert.pop();

		sum += (p + toInsert.size()) * get<2>(top);
	}

	cout << sum;

	return 0;
}