세종 병원

https://code.sasa.hs.kr/problem.php?id=2452 

 

풀이의 개요는 다음과 같다.

1. 손님들을 응급환자,예약환자,일반환자로 구분을 하여 각기 다른 큐에 집어넣는다.

scanf("%d : %d") 를 이용해 시간을 효과적으로 입력받는다. 

시간이 HH:MM꼴로 되어 있을 텐데 time = HH*60 + MM으로 나타내어 선후관계를 파악하기 쉽게 한다.

세종이의 '도착 시점'을 이때 기록해놓아야 한다.

 

2. 이때 큐는 '줄을 서기 시작하는 시점'을 우선순위로 하여 가장 빠른 사람을 dequeue하는 우선순위큐여야 한다.

우선순위큐의 원소는 구조체이며, 구조체간 비교 연산이 정의되어야 한다.

 

3. 환자들을 한명씩 진료한다. 이때 각 사람의 진료가 끝나는 시점을 기록하여 '현재 시간'을 갱신해준다.

이때 진료의 순서를 정하는 방법은 응급환자부터 차례대로 보면서  현재 시간보다 줄 서는 시점이 앞이라면 

바로 진료를 시작하고, 모든 환자가 만약 현재 시간 후에 줄 서기를 시작했다면 가장 먼저 줄을 선 사람을 진료한다.

 

이를 반복하다 '세종이'를 만나는 순간의 현재 시간이 바로 세종이가 진료받기 시작하는 시점이다.

 

time = 진료받기 시작하는 시점 - 도착한 시점 을 출력하면 그것이 곧 정답이다.

//pentagon03
#include<stdio.h>
#include<queue> //우선순위큐
#include<algorithm> //min,max 함수
using namespace std;
const int type=3;
//Pat은 환자의 정보를 저장. (Patient)
struct Pat{
    int n,t,w; //도착 순서, 줄 서는 시간, 진료 시간
    //일반적으로 우선순위큐는 '최대힙'으로 구현이 되어 있다. 
    //우리가 필요한 것은 '최소 원소'이기 때문에 대소 비교를 거꾸로 해줌으로써
    //priority_queue<Pat>이 최소 원소를 뽑아내게 할 수 있다.
    //아래는 대소 비교 연산자 '<'을 정의한 것이다.
    bool operator <(const Pat&tmp) const{
        if(t==tmp.t)
            return n>tmp.n;
        return t>tmp.t;
    }
};
//우선순위큐이다. pq[3]은 응급 환자, pq[2]는 예약 환자, pq[1]은 일반 환자이다.
priority_queue<Pat> pq[4];
int main(){
    int n,m; 
    scanf("%d%d",&n,&m); 
    int arrived_time,heal_start_time; //세종이가 줄을 서기 시작하는 시점, 진료받기 시작하는 시점이다.
    for(int i=1,f,s1,s2,e1,e2,w;i<=n;i++){
        //입력 형식 f s1:s2 e1:e2 w 
        //순서대로 환자 종류, 도착 시점, 예약 시점, 진료하는데 걸리는 시간
        scanf("%d %d:%d %d:%d %d",&f,&s1,&s2,&e1,&e2,&w);
        //시점을 분 단위로 변환 
        //00:00을 기준으로 몇분이 지났는지를 각 변수 s,e가 저장한다.
        int s=s1*60+s2,e=e1*60+e2;
        //세종이의 도착시점 처리 
        if(i==m) arrived_time=s;
        int t;
        //f : 3->응급환자, 2->예약환자, 1->일반 환자
        if(f==2){
            //지각생 처리 
            if(s>e) f=1,t=s; //일반환자로 전락
            else t=e; //예약시간에 줄을 선다
        }
        else t=s; //도착시간에 줄을 선다
        pq[f].push({i,t,w});
    }
    //현재 살펴보고 있는 시간
    int current_time=0;
    while(1){
        //현재 가장 먼저 진료받을 환자를 정한다.
        int min_id,min_time=1e9;
        // type은 환자의 종류의 수이다. 여기서는 type=3
        for(int i=type;i>=1;i--){
            if(pq[i].empty()) continue;
            int x=pq[i].top().t;
            //현재 시간 전부터 진료를 기다리고 있었다면 바로 진료를 진행한다. 
            //응급환자,예약환자,일반환자 순으로 우선순위가 높기 때문이다.
            if(x<=current_time){
                min_id=i;
                break;
            }
            //아직 아무도 줄을 서지 않은 상태라면 가장 줄서기 시점이 빠른 환자를 고른다.
            else{
                if(x<min_time)
                    min_time=x,min_id=i;
            }
        }
        //min_id는 환자의 종류(3,2,1). 우선순위큐에서 환자를 pop해주어야 한다.
        Pat cur=pq[min_id].top(); pq[min_id].pop();
        //환자가 도착한 시간과 현재 시간 중 더 큰 값이 환자가 진료받기 시작하는 시점이다.
        current_time = max(current_time,cur.t);
        if(cur.n==m){
            heal_start_time=current_time;
            break;
        }
        //진료가 끝났다면 시간을 갱신해준다.
        current_time+=cur.w;
    }
    //와! 드디어 출력
    int ans=heal_start_time-arrived_time;
    printf("%d",ans);
}