[BOJ] 백준 17612 쇼핑몰

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

[그래프] 힙(Heap) 자료구조란? 

힙(Heap) 자료구조란?

먼저 대기하고 있는 고객이 계산대에서 물건을 계산하고 쇼핑몰을 빠져 나갑니다.

→ FIFO (First In First Out)

- 계산대가 2개이상 동시에 비는 경우 낮은 번호 계산대에 먼저 배정

  ex) 3번, 5번 계산대가 비게된다면 3번으로 안내

- 계산이 동시에 끝나는 경우에는 (출구에 가까운)높은 번호 계산대에 있는 고객이 먼저 빠져나갑니다.

  ex) 4번, 10번 계산대에서 동시에 계산이 끝난다면 10번 고객이 먼저 쇼핑몰을 나갑니다.

 

두 경우의 우선순위가 다르므로 두 개의 우선순위 큐를 이용합니다.

- 계산대로 들어가는 고객을 위한 우선순위 큐(minpq)

- 계산대로부터 나온 고객을 위한 우선순위 큐(maxpq)

 

문제 접근

① N과 K중 작은 수만큼 계산대에 대기자 매칭

    ex) 계산대 3대 중에 대기자가 2명인 경우

          2명이 대기 없이 계산대에 배정

    ex) 계산대 3대 중에 대기자가 5명인 경우

          3명만 계산대 배정받고 나머지 2명은 대기

② 대기중인 고객에 대하여 minpq에서 한 명 꺼낼 때마다 꺼낸 고객은 maxpq에 넣고

    빈 계산대에는 대기중인 고객을 순차적으로 넣는다.

③ 대기 중인 고객이 없다면 minpq에 남은 고객을 모두 꺼내어 maxpq에 넣는다.

④ 모든 고객이 maxpq에 모이면 우선순위에 맞게 모두 꺼내면서 출력 값을 계산한다.

 

시뮬레이션

고객: 10명 / 계산대: 3개

- 고객정보를 입력받을 때:

- 계산 처리(우선순위큐 In/Out) 과정:

  ※ 계산 완료 시간 = 대기시간 + 계산 소요 시간

 

① 고객 3명이 계산대에 낮은 번호 계산대로 순차적으로 배정

minpq = [(123, 4, 1) / (21, 5, 2) / (34, 14, 3)]

maxpq = []

 

② 대기하는 고객이 없도록하기 위해서

   minpq에서 계산이 끝나는 사람마다 고객 한명이 나갑니다. (maxpq에 넣습니다.)

   빈 계산대에 대기하고 있던 고객 한명이 들어갑니다. (minpq에 넣습니다.)

[1초]: 1번 계산대에서 56번 고객이 먼저 나가고 그 자리에 새로운 고객이 들어갑니다.

         이때, 123번 고객이 계산완료까지 걸리는 시간 = 4 + 1 = 5

minpq = [(56, 5, 1) / (34, 14, 3) / (21, 5, 2)]

maxpq = [(123, 4, 1)]

 

[5초]: 1, 2번 계산대에서 동시에 계산 완료되는 고객이 2명 발생합니다.

          문제 원칙상에서는 높은 번호에 있는 사람이 먼저 빠져나가야 하지만

          구현된 minpq에서는 낮은 번호 계산대가 우선순위가 높기에 1번 계산대 고객이 먼저 maxpq에 빠져나갑니다

          (추후에 maxpq에서 pop()과정에서 시간대가 동일한 경우 높은 번호가 우선순위 높도록 처리됨

          ※ heap 구조에서는 root값을 pop하면서 원소들을 재정렬됨)

minpq = [(21, 5, 2) / (34, 14, 3) / (45, 12, 1)]

maxpq = [(123, 4, 1) / (56, 5, 1)]

 

[5초]:2번 계산대: 21번 고객 OUT / 34번 고객 IN

minpq = [(723, 10, 2) / (34, 14, 3) / (45, 12, 1)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2)]

 

[10초]: 2번 계산대: 723번 고객 OUT / 55번 고객 IN

minpq = [(45, 12, 1) / (34, 14, 3) / (55, 17, 2)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2)]

 

[12초]: 1번 계산대: 45번 고객 OUT / 13번고객인 IN

minpq = [(34, 14, 3) / (55, 17, 2) / (13, 17, 1)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2) / (45, 12, 1)]

 

[14초]: 3번 계산대: 34번 고객 OUT / 910번 고객 IN

minpq = [(13, 17, 1) / (55, 17, 2) / (910, 24, 3)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2) / (45, 12, 1) / (34, 14, 3)]

 

[17초]:  1번 계산대: 13번 고객 OUT / 73번 고객 IN

minpq = [(55, 17, 2) / (910, 24, 3) / (73, 20, 1)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2) / (45, 12, 1) / (34, 14, 3) / (13, 17, 1)]

 

③ 대기하고 있는 고객은 없으면 현재 계산대에 있는 고객들만 완료하면 됩니다.

    즉, minpq를 비워가며 maxpq에 옮겨줍니다.

[17초]: 2번 계산대 55번 고객 OUT

minpq = [(73, 20, 1) / (910, 24, 3)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2)

                 (45, 12, 1) / (34, 14, 3) / (13, 17, 1) / (55, 17, 2)]

[20초]: 1번 계산대 73번 고객 OUT

minpq = [(910, 24, 3)]

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2) / (45, 12, 1) 

                / (34, 14, 3) / (13, 17, 1) / (55, 17, 2) / (73, 20, 1)]

[24초]: 3번 계산대 910번 고객 OUT

minpq = []

maxpq = [(123, 4, 1) / (56, 5, 1) / (21, 5, 2) / (723, 10, 2) / (45, 12, 1)

                 / (34, 14, 3) / (13, 17, 1) / (55, 17, 2) / (73, 20, 1) / (910, 24, 3)]

 

④ maxpq에서 계산이 먼저 완료된 고객을 순서대로 pop()합니다.

    (계산 완료 시간이 동일한 경우 계산대 번호가 높은 고객이 우선순위를 가집니다.)

    

▶ (123, 4, 1) - (21, 5, 2) - (56, 5, 1) - (723, 10, 2) - (45, 12, 1) 

    - (34, 14, 3) - (55, 17, 2) - (13, 17, 1) - (73, 20, 1) - (910, 24, 3)

    (정답을 출력할 때는 1×r1 + 2×r2 + ... + N×rN 값 출력)

---

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
 
const int LM = 300100;
typedef long long LL;
typedef struct {
    int id, calcTime, desk;
} Info;
 
bool max(const Info& a, const Info& b) {
    if (a.calcTime != b.calcTime) return a.calcTime < b.calcTime;
    return a.desk > b.desk;
}
 
bool min(const Info& a, const Info& b) {
    if (a.calcTime != b.calcTime) return a.calcTime < b.calcTime;
    return a.desk < b.desk;
}
 
void swap(Info& a, Info& b) { Info t = a; a = b; b = t; }
 
struct PriorityQueue {
    Info heap[LM];
    int hn;
    bool(*cmp)(const Info&, const Info&);
    void init(int order) {
        hn = 0;
        cmp = order ? max : min;
    }
 
    Info top() { return heap[1]; }
    bool empty() { return hn == 0; }
    int size() { return hn; }
    void push(Info data) {
        heap[++hn] = data;
        int c = hn;
        while (c > 1 && cmp(heap[c], heap[c / 2])) {
            swap(heap[c], heap[c / 2]);
            c /= 2;
        }
    }
 
    void pop() {
        int p = 1, c = 2;
        swap(heap[1], heap[hn--]);
        for (; c <= hn; p = c, c *= 2) {
            if (c < hn && cmp(heap[c + 1], heap[c])) c++;
            if (!cmp(heap[c], heap[p])) break;
            swap(heap[c], heap[p]);
        }
    }
}maxpq, minpq;
 
int N, K;
LL ans;
 
int main() {
    // freopen("input.txt", "r", stdin);
    maxpq.init(1);
    minpq.init(0);
    scanf("%d %d", &N, &K);
    int i, id, tm;
 
    // min(N, K)명의 고객을 minpq에 넣는다.
    for (i = 1; i <= K && i <= N; ++i) {
        scanf("%d %d", &id, &tm);
        minpq.push({ id, tm, i });
    }
 
    // 처음에 들어가지 못한 대기자들 처리
    // 계산대에서 한명씩 빠지면 그 계산대에 제일 앞에 있는 대기자를 배정
    // 대기자 정보 = {ID, 계산 완료 시간, 계산대 번호}
    // 계산 완료시간 = 가지고 있는 물건 계산시간 + 해당 계산대에 지금까지 누적된 시간 
    for (; i <= N; ++i) {
        Info t = minpq.top(); minpq.pop();
        maxpq.push(t);
        scanf("%d %d", &id, &tm);
        minpq.push({ id, t.calcTime + tm, t.desk });
    }
 
    // 현재 대기자는 없으면 계산하고 있는 사람들을 모두 처리
    while (!minpq.empty()) {
        Info t = minpq.top();
        minpq.pop();
        maxpq.push(t);
    }
 
    for (i = 1; i <= N; ++i) {
        Info t = maxpq.top();
        ans += (LL)t.id * i;
        maxpq.pop();
    }
 
    printf("%lld\n", ans);
}