문제

대형 쇼핑몰에서 쇼핑을 마친 N명의 고객들이 계산을 하고 쇼핑몰을 떠나고자 계산대 앞에 줄을 서 있다. 각 고객은 커다란 짐수레(cart)에 물건을 담아 계산대로 간다. 쇼핑몰에는 아래 그림과 같이 K개의 계산대가 병렬로 배치되어 있다. 쇼핑몰 안내원들은 계산대에 온 사람들을 가장 빨리 계산을 마칠 수 있는 계산대로 안내를 한다. 안내원은 각 계산대에서 기다리고 있는 사람들이 계산을 하는데 얼마나 걸리는지 이미 알고 있다.

안내원이 고객을 계산대로 안내할 때 두 계산대에서 기다려야 할 시간이 같을 경우에는 가장 번호가 작은 계산대로 안내를 한다. 즉 3번, 5번 계산대에서 기다릴 시간이 똑같이 15분으로 최소일 경우에는 3번으로 안내를 한다.

계산을 마친 고객은 출구를 통하여 쇼핑몰을 완전히 빠져 나간다. 만일 계산대에서 계산을 마친 고객의 시간이 동일하다면 출구에 가까운 높은 번호 계산대의 고객부터 먼저 빠져나간다. 예를 들어 두 계산대 4번과 10번에서 두 고객이 동시에 계산을 마쳤다면 계산대의 번호가 더 높은 10번 계산대의 고객이 먼저 쇼핑몰을 나간다. 물건을 계산하는 데에는 종류에 관계없이 동일하게 1분이 소요된다. 즉, 물건이 w개 있는 손님이 계산을 마치는 데에는 정확히 w분이 소요된다.

여러분은 계산대로 들어가기 위하여 줄을 서 있는 고객 N명의 정보( 회원번호, 구매한 물건의 수)를 알고 있을 때, 이들이 계산을 하고 쇼핑몰을 빠져나오는 순서를 구해야 한다. 계산대로 들어가고 계산대에서 나오는데 걸리는 시간은 없다고 가정한다.

입력

• 입력의 첫 줄에는 2개의 정수 N(1 ≤ N ≤ 100,000)과 k(1 ≤ k ≤ 100,000)가 주어진다. 다음 줄부터 N개의 줄에 걸쳐 고객 N명의 정보가 줄 맨 앞의 고객부터 맨 뒤 고객까지 순서대로 주어진다. i번째 줄은 줄의 앞에서 i번째 고객의 회원번호 $id_i$(1 ≤ $id_i$ ≤ 1,000,000)와 그가 구입한 물건의 수 $w_i$(1 ≤ $w_i$ ≤ 20)로 이루어져 있다. N명의 회원번호는 모두 다르다.

출력

• 고객 N명의 회원번호를 쇼핑몰을 빠져나가는 순서대로 $r_1, r_2, \cdots, r_N$ 이라 할 때,
  $1×r_1 + 2×r_2 + \cdots + N×r_N$ 의 값을 출력한다. 출력값이 int 범위를 넘어갈 수 있음에 유의하라.

---

0. 전체적인 풀이 요약

• pair<int, int>를 element로 갖는 우선순위 큐(Priority Queue)를 이용하였다.
• 대기시간이라고 생각하지말고, 계산이 0분에 시작했다고 했을 때, 해당 사람이 계산을 끝마치는 시간이라고 생각하면 풀이가 훨씬 편해진다.
• 문제를 크게 두 부분으로 나누어서 풀이하였다.
  1. 손님들의 입장 (줄 세우기): 계산대로 들어갈 때에는 대기시간이 짧은, 대기시간이 같다면 계산대 번호가 작은 계산대로 들어가는 것이 원칙이므로, 처음 우선순위 큐를 선언할 때 greater<pair<int, int>>를 사용하면 된다. 물론 pair의 순서는 (대기시간, 계산대번호)순이다.
  2. 손님들의 퇴장(출력 결과값 구하기): 계산대에서 나올 때는 대기시간이 짧은, 대기시간이 같다면 계산대번호가 큰 계산대에서 먼저 나온다. 따라서, 우선순위 큐에 우리가 직접 만든 Custom Compare를 넣어주어야 한다.

1. 손님들 입장시키기 (줄 세우기)

• 우선, vector를 이용하여 계산대를 표현하자. 계산대 앞에 선 줄은 각각 queue로 표현된다. 즉, vector 한칸 한칸마다 queue가 들어가 있는 것이다.
  vector<queue<pair<int, int>>> line(K);

• 또한, 다음 손님이 들어갈 계산대를 구하기 위한 최소 힙을 구현해준다.
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> enter_pq;

• 각 계산대에 한 사람씩 줄을 일단 세운다. 여기서, 계산대의 개수가 사람 수보다 많다면 예외처리 해준다.

• i번 계산대 줄의 첫 사람의 정보는 (대기시간, 회원번호)로 넣어주고,
  최소 힙에 넣을 때는 (대기시간, 줄 서있는 계산대번호)를 넣어준다.

  int main() { int N, K; int id, w; bool many_cashier = false; long long result = 0; scanf("%d %d", &N, &K); vector<queue<pair<int, int>>> line(K); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> enter_pq; // 계산대의 개수만큼 줄을 세운다. for (int i = 0; i < K; i++) { //계산대가 손님 수보다 많은 경우 예외처리 if (i >= N) { many_cashier = true; break; } scanf("%d %d", &id, &w); line[i].push(make_pair(w, id)); enter_pq.push(make_pair(w, i)); }

• 만약, 손님 수 > 계산대 수(many_cashier == false) 라면, K+1번째 손님부터 다시 줄 세우기 시작.
• 다음 손님이 줄을 서게 될 계산대는 enter_pq의 top에 있는 손님이 줄 서고 있는 계산대이다. 또한, 다음 손님이 계산을 끝마치게 될 시간은 그 계산대의 앞에 있는 사람이 계산을 끝마치는 시간 + 자신의 계산시간 이므로, waitingTime을 그렇게 구한다.
  nextLine = enter_pq.top().second;
waitingTime = enter_pq.top().first + w;
• 이렇게 구해놓은 다음 손님의 정보를 가지고 이 손님을 nextLine번째 계산대에 줄을 세운다. 또, enter_pq.top()에 있던 손님은 계산을 마친것으로 간주하므로 enter_pq.pop()을 한 번 해주고, 이번에 새로 들어갈 손님을 enter_pq에 push해준다.
• 여기까지 하면 모든 사람들에 대한 각자 자기에게 맞는 계산대에 줄 세우기가 완료된다.

if (many_cashier == false) { for (int i = K; i < N; i++) { scanf("%d %d", &id, &w); int nextLine, waitingTime; nextLine = enter_pq.top().second; waitingTime = enter_pq.top().first + w; line[nextLine].push(make_pair(waitingTime, id)); enter_pq.pop(); enter_pq.push(make_pair(waitingTime, nextLine)); } }

2. 손님들 퇴장시키기 (출력 결과값 구하기)

• 우선, 손님들을 퇴장시키기 위한 정렬(조건은 0-2번 참고)은 STL에서 지원해주지 않으므로 직접 만들어 써야한다.
• 이 정렬을 적용한 새로운 우선순위 큐 result_pq를 만들어주자.
  priority_queue<pair<int, int>, vector<pair<int, int>>, compare> result_pq;

struct compare { //연산자 오버로딩 bool operator()(pair<int, int> &a, pair<int, int> &b) { if (a.first == b.first) { return a.second < b.second; } else return a.first > b.first; } };

• 이제 각 계산대 줄의 맨 앞 사람들을 결과 우선순위 큐(result_pq)에 넣어주자. 결과 큐에 넣어줄 때는
  (계산 끝마치는 시간, 계산대번호)의 쌍으로 넣어준다. 마찬가지로 계산대 수가 손님 수보다 더 많으면 예외처리.

for (int i = 0; i < K; i++) { //계산대가 손님 수보다 더 많은 경우 예외처리 if (i >= N) break; result_pq.push(make_pair(line[i].front().first, i)); }

• 이제 결과값을 구하기 위해 1부터 N까지 for문을 돌린다.
• result_pq.top().second에 저장된 계산대 번호와, 그 계산대의 줄 맨 앞에 있는 사람의 회원번호를 알아낸다.
  lineNum = result_pq.top().second;
customerId = line[lineNum].front().second;
• 이제 result_pq의 맨 앞에 있는 사람을 pop하고, 해당 계산대의 줄에서도 pop한다.
• 해당 계산대의 그 다음 사람을 result_pq에 넣어야하므로, 해당 계산대가 비어있지 않은 경우라면 다시 result_pq에 push한다.

for (int i = 1; i <= N; i++) { int lineNum, customerId; lineNum = result_pq.top().second; customerId = line[lineNum].front().second; result += (long long)i * (long long)customerId; result_pq.pop(); line[lineNum].pop(); //해당 계산대가 비어있지 않은 경우에만 다시 result_pq에 push한다. if (!line[lineNum].empty()) { result_pq.push(make_pair(line[lineNum].front().first, lineNum)); } }

3. 전체 소스코드

#include <iostream> #include <queue> #include <vector> #include <algorithm> using namespace std; struct compare { //연산자 오버로딩 bool operator()(pair<int, int> &a, pair<int, int> &b) { if (a.first == b.first) { return a.second < b.second; } else return a.first > b.first; } }; int main() { int N, K; int id, w; bool many_cashier = false; long long result = 0; scanf("%d %d", &N, &K); vector<queue<pair<int, int>>> line(K); priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> enter_pq; // 계산대의 개수만큼 줄을 세운다. for (int i = 0; i < K; i++) { //계산대가 손님 수보다 많은 경우 예외처리 if (i >= N) { many_cashier = true; break; } scanf("%d %d", &id, &w); line[i].push(make_pair(w, id)); enter_pq.push(make_pair(w, i)); } //만약 계산대가 손님 수보다 적다면 // K+1번째 손님부터 다시 줄세우기 시작 //해당 계산대의 대기시간을 업데이트, 기존 손님 out, 새로운 손님 in if (many_cashier == false) { for (int i = K; i < N; i++) { scanf("%d %d", &id, &w); int nextLine, waitingTime; nextLine = enter_pq.top().second; waitingTime = enter_pq.top().first + w; line[nextLine].push(make_pair(waitingTime, id)); enter_pq.pop(); enter_pq.push(make_pair(waitingTime, nextLine)); } } //줄세웠던 것을 다시 결과 큐로 넣는 작업 priority_queue<pair<int, int>, vector<pair<int, int>>, compare> result_pq; for (int i = 0; i < K; i++) { //계산대가 손님 수보다 더 많은 경우 예외처리 if (i >= N) break; result_pq.push(make_pair(line[i].front().first, i)); } for (int i = 1; i <= N; i++) { int lineNum, customerId; lineNum = result_pq.top().second; customerId = line[lineNum].front().second; result += (long long)i * (long long)customerId; result_pq.pop(); line[lineNum].pop(); //해당 계산대가 비어있지 않은 경우에만 다시 result_pq에 push한다. if (!line[lineNum].empty()) { result_pq.push(make_pair(line[lineNum].front().first, lineNum)); } } printf("%lld\n", result); }

4. 배운 것

1. vector의 원소로 queue를 넣을 수 있다는 것... C로만 문제를 풀어오다가 신세계를 만난 기분이다.
2. pair를 활용하여 문제를 풀면 상당히 편리하다는 것. 이 역시 C로만 문제를 풀어오다가(이 때는 구조체를 사용) 고민이 싹 해결된 것 같은 느낌이었다.

cf) 참고: https://everenew.tistory.com/106