[SWEA] 2477 : 차량정비소

2477 : 차량정비소

풀이

구현

배열과 큐와 벡터를 이용해 하란대로 그대로 구현했다.

결과가 92ms인데 다른 코드 중에 12ms가 있다.

더 효율적인 방법도 생각해봐야겠다.

디버깅없이 한번에 구현해서 맞혔다. 기분좋다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int T;
    cin>>T;
    for(int tc=1;tc<=T;tc++){
        vector<int> ans;
        int n,m,k,a,b;
        cin>>n>>m>>k>>a>>b;
        int rc[21]={0}; //각접수처 처리시간
        int ma[21]={0}; //각 정비소 처리시간
        int pt[1001]={0}; //고객 도착시간
        for(int i=1;i<=n;i++){
            cin>>rc[i];
        }
        for(int i=1;i<=m;i++){
            cin>>ma[i];
        }
        for(int i=1;i<=k;i++){
            cin>>pt[i];
        }
        //고객 도착 큐 (고객번호)
        priority_queue<int,vector<int>,greater<int>> q1;
        //고객 정비대기 큐 (고객번호, 출신접수처)
        queue<pair<int,int>> q2;
        //접수처 벡터 (고객번호,남은시간)
        vector<pair<int,int>> v1(21,{0,0});
        //정비소 벡터 (고객번호,남은시간)
        vector<pair<int,int>> v2(21,{0,0});
        int t=0;
        int finish=0;
        while(finish<k){
            //도착고객 큐에 넣기
            for(int i=1;i<=k;i++){
                if(pt[i]<=t){
                    q1.push(i);
                    pt[i]=10000;
                }
            }
            //접수처에 도착대기중 고객 넣거나 남은시간1빼기->0되면 정비대기큐로
            for(int i=1;i<=n;i++){
                //비었으면 접수
                if(v1[i].first==0){
                    if(!q1.empty()){
                        v1[i].first=q1.top();
                        v1[i].second=rc[i];
                        q1.pop();
                    }
                }
                //안비었으면 시간빼기
                else{
                    //1뻄
                    //if 0되면
                    //빼고 if(!q1.empty())면 바로추가
                    v1[i].second--;
                    if(v1[i].second==0){
                        q2.push({v1[i].first,i});
                        v1[i].first=0;
                        if(!q1.empty()){
                            v1[i].first=q1.top();
                            v1[i].second=rc[i];
                            q1.pop();
                        }
                    }
                }
            }
            //정비소에 정비대기중 고객 넣거나 남은시간1빼기->0되면 비움(finish추가)
            //고객을 넣을때 출신접수처(q2의 second)가 a이면서 b정비소로 가면
            //ans벡터에 넣기.
            for(int i=1;i<=m;i++){
                //비었으면 정비
                if(v2[i].first==0){
                    if(!q2.empty()){
                        v2[i].first=q2.front().first;
                        v2[i].second=ma[i];
                        if(a==q2.front().second && b==i){
                            ans.push_back(q2.front().first);
                        }
                        q2.pop();
                    }
                }
                //안비었으면 시간빼기
                else{
                    v2[i].second--;
                    if(v2[i].second==0){
                        finish++;
                        v2[i].first=0;
                        if(!q2.empty()){
                            v2[i].first=q2.front().first;
                            v2[i].second=ma[i];
                            if(a==q2.front().second && b==i){
                                ans.push_back(q2.front().first);
                            }
                            q2.pop();
                        }
                    }
                }
            }
            t++;
        }
        int sum=0;
        if(ans.size()==0)
            sum=-1;
        for(int i=0;i<ans.size();i++){
            sum+=ans[i];
        }
        cout<<'#'<<tc<<' '<<sum<<'\n';
    }
    return 0;
}

Written on March 27, 2019