[BOJ / C++] #17225 세훈이의 선물가게

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

🎁 문제 풀이

• 각 주문을 받으면서 차례대로 선물의(포장 시작 시간, 색깔) 구조체를 구조체 우선순위 큐에 넣어주면 된다.

• 이때 주문마다 포장할 물건의 개수와, 포장하는 사람, 포장하는 데 걸리는 시간이 다르다.
  만약 상민이가 받은 주문이
  t시점에 시작되고 , 하나를 포장하는 데 A만큼 걸리고, 총 3개를 포장해야 한다면
  우선순위 큐에 넣어줘야 하는 선물 구조체는 총 3개이고 시작 시점은 각각 t, t+A, t+2*A 이렇게 될 것이다.

• 이후 우선순위 큐로 정렬 된 구조체를 하나씩 pop하면서, 순서대로 선물 번호를 붙여주면 된다.
  이때 상민벡터, 지수벡터를 만들어 색깔에 따라 상민벡터 혹은 지수벡터에 push해주면
  누가 어떤 선물을 포장했는지 알 수 있다.

100점까진 수월했으나 140점 받기가 까다로웠다 🥲

1. 포장 시간 시작 기준으로 선물 번호를 붙이는 것.. 처음엔 끝나는 시간으로 붙이느라 틀렸다.

2. 현재 t초에 주문이 들어왔을 때, 이전 주문의 포장작업이 아직 끝나지 않았으면 바로 t초에 포장을 시작할 수 없다..! 그래서 이전 주문이 끝나는 시간을 계속 업데이트 해두고, 이전 주문이 끝나는 시간>t 이면, 현재 주문은 이전 주문이 끝나는 시간에 시작해야 한다!!!!

구조체

struct Order{ 
    int time; // 포장 시작 시간
    char color; // 색깔
    Order(int t, int c) {
        time = t;
        color = c;
    }
    bool operator <(const Order &b)const{
        if(time==b.time) return color>b.color; //시간이 같으면 상민이가 먼저 시작
        return time>b.time; //최소힙
    }
};

우선순위 큐의 정렬 기준 문제에 의해 다음과 같다.
1. 포장 시작 시간이 같을 경우 상민이가 먼저 포장 (min Heap의 더 최상위에 존재하도록)
2. 포장 시작 시간의 오름차순 기준으로 선물 번호를 붙여줘야 하므로 time기준으로 min Heap 생성.

주문 받기

 priority_queue <Order> pq;

    //만약에 상민이한테 1,2번 주문이 들어온다하자.
    //1번 주문을 포장하고 있는 중에 2번 주문이 들어오면, 1번이 끝나지 않으면 바로 시작(t)할 수 없으므로
    //1번 주문이 끝나는 시점을 기억하고 있다가 그때부터 시작해야 한다.
    int bEnd=-1;
    int rEnd=-1;
    for(int i=0;i<N;i++){
        int t,n;char c;
        cin>>t>>c>>n;

        if(c=='B'){
            if(bEnd>t) t=bEnd; // 아직 앞 주문이 끝나지 않은 상태라면
            for(int j=0;j<n;j++){
                pq.push(Order((t+A*j),'B')); //(✨포장 시작 시간, 색깔)
            }
            bEnd=(t+A*n); //현재 주문이 끝나는 시간 업데이트

        }else if(c=='R') {
            if(rEnd>t) t=rEnd; // 아직 앞 주문이 끝나지 않은 상태라면

            for (int j = 0; j <n; j++) {
                pq.push(Order((t+B*j), 'R')); //(✨포장 시작 시간, 색깔)
            }
            rEnd=(t+B*n); //현재 주문이 끝나는 시간 업데이트
        }

bEnd : 상민이의 이전주문이 끝나는 시간
rEnd : 지수의 이전주문이 끝나는 시간

🎁 코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct Order{
    int time;
    char color;
    Order(int t, int c) {
        time = t;
        color = c;
    }
    bool operator <(const Order &b)const{
        if(time==b.time) return color>b.color; //시간이 같으면 상민이가 먼저 시작
        return time>b.time; //최소힙
    }
};

int main(){
    int A, B, N;
    cin>>A>>B>>N;

    priority_queue <Order> pq;

    //만약에 상민이한테 1,2번 주문이 들어온다하자.
    //1번 주문을 포장하고 있는 중에 2번 주문이 들어오면, 1번이 끝나지 않으면 바로 시작(t)할 수 없으므로
    //1번 주문이 끝나는 시점을 기억하고 있다가 그때부터 시작해야 한다.
    int bEnd=-1;
    int rEnd=-1;
    for(int i=0;i<N;i++){
        int t,n;char c;
        cin>>t>>c>>n;

        if(c=='B'){
            if(bEnd>t) t=bEnd; // 아직 앞 주문이 끝나지 않은 상태라면
            for(int j=0;j<n;j++){
                pq.push(Order((t+A*j),'B')); //(✨포장 시작 시간, 색깔)
            }
            bEnd=(t+A*n); //현재 주문이 끝나는 시간 업데이트

        }else if(c=='R') {
            if(rEnd>t) t=rEnd; // 아직 앞 주문이 끝나지 않은 상태라면

            for (int j = 0; j <n; j++) {
                pq.push(Order((t+B*j), 'R')); //(✨포장 시작 시간, 색깔)
            }
            rEnd=(t+B*n); //현재 주문이 끝나는 시간 업데이트
        }
    }

    vector<int> sangmin;
    vector<int> jisu;

    int idx=1;
    while(!pq.empty()){

        //cout<<"["<<idx<<"] time : "<<pq.top().time<<" color : "<<pq.top().color<<"\n";

        char color=pq.top().color;
        pq.pop();
        if(color=='B'){
            sangmin.push_back(idx);
        }else{
            jisu.push_back(idx);
        }
        idx++;
    }
    cout<<sangmin.size()<<"\n";
    for(int i=0;i<sangmin.size();i++){
        cout<<sangmin[i]<<" ";
    }

    cout<<"\n"<<jisu.size()<<"\n";
    for(int i=0;i<jisu.size();i++){
        cout<<jisu[i]<<" ";
    }
    cout<<"\n";
    return 0;
}