[BOJ / C++] #17225 세훈이의 선물가게
https://www.acmicpc.net/problem/17225
🎁 문제 풀이
-
각 주문을 받으면서 차례대로 선물의
(포장 시작 시간, 색깔)
구조체를 구조체우선순위 큐
에 넣어주면 된다. -
이때 주문마다 포장할 물건의 개수와, 포장하는 사람, 포장하는 데 걸리는 시간이 다르다.
만약 상민이가 받은 주문이
t시점에 시작되고 , 하나를 포장하는 데 A만큼 걸리고, 총 3개를 포장해야 한다면
우선순위 큐에 넣어줘야 하는 선물 구조체는 총 3개이고 시작 시점은 각각 t, t+A, t+2*A 이렇게 될 것이다. -
이후 우선순위 큐로 정렬 된 구조체를 하나씩 pop하면서, 순서대로 선물 번호를 붙여주면 된다.
이때 상민벡터, 지수벡터를 만들어 색깔에 따라 상민벡터 혹은 지수벡터에 push해주면
누가 어떤 선물을 포장했는지 알 수 있다.
100점까진 수월했으나 140점 받기가 까다로웠다 🥲
-
포장 시간 시작 기준으로 선물 번호를 붙이는 것.. 처음엔 끝나는 시간으로 붙이느라 틀렸다.
-
현재 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;
}
Author And Source
이 문제에 관하여([BOJ / C++] #17225 세훈이의 선물가게), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inryu/BOJ-C-17225-세훈이의-선물가게저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)