[SW Expert Academy] 2477. [모의 SW 역량테스트] 차량 정비소 풀이 (C++)

2017.10.20. 에 쓰여진 글입니다.

---

문제링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy&categoryId=AV6c6bgaIuoDFAXy&categoryType=CODE

SW Expert Academy

 

풀이방법

현재시간==고객 도착시간 -> 접수창구 대기열 큐 (a_wait)에 넣어줌 -> 접수창구벡터(a)에 넣어줌

-> 접수창구에서 일 끝난사람 -> 정비창구 대기열 큐 (b_wait)에 넣어줌 -> 정비창구벡터(b)에 넣어줌 

-> 정비창구에서 볼일 끝남 -> 현재시간 증가

while이 한번 돌면 위에 순서로 돌아감.

이때 정답에서 원하는 A와 B창구를 이용하면 A접수창구 이용손님 (a_use), B정비창구 이용손님 (b_use)벡터에 해당 손님 번호를 넣어줌.

이런식으로 정답을 찾는데 이제 각 창구에서 어떻게 처리하느냐가 관건임

a벡터와 b벡터를 만들었는데 어차피 똑같으니까 a벡터로 설명함.

벡터에 3개의 값을 묶어서 넣어줌.

(남은시간, 창구처리시간, 이용중인고객)

이 3개를 묶어서 넣어줌. 예를 들어 1번창구의 처리시간이 10초라고 해보겠음

그러면 (10,10,-1) 을 초기값으로 설정해줌. 그리고 만약에 해당 창구로 1번 고객이 들어간다면

(10,10,1)을 만들어줌. 그리고 매초마다 (9,10,1) (8,10,1) (7,10,1) (6,10,1) ... (0,10,1) 까지 바꿔주는것임

그래서 결국 0이되면 해당 처리가 끝난거고 손님 정비창구 대기열로 넣어주고 (10,10,-1)로 초기화 시키고 다음 손님을 받는것임

이렇게해서 정비창구까지 끝내면 차량정비가 끝남.

시뮬레이션같은 문제였는데 은행창구에서 볼일보는거 코드로 짜는 느낌이었음.

 

 

 

소스코드

#include <iostream>
#include <vector>        //vector 위한 헤더
#include <queue>        //queue 위한 헤더
#include <utility>        //pair 위한 헤더
 
using namespace std;
 
enum { EMPTY = -1 };
 
int N, M, K, A, B;
vector < pair < pair < int, int > , int > > a, b;    
//((현재 창구 이용중이라면 남은 시간, 현재 창구 처리 시간),현재 창구 이용고객)
queue < int > a_wait, b_wait;    //a대기열 큐, b대기열 큐
vector < int > a_use, b_use;    //a창구 이용한손님 저장하는 벡터, b창구 이용한 손님 저장하는 벡터
int customer[1001];                //해당 고객이 도착한 시간
int cur_time;                    //현재시간
int Answer;                        //정답
int a_number, b_number;            //a창구 이용한 고객, b창구 이용한 고객
 
void Init()
{
    for (int i = 0; i < 1001; i++)
        customer[i] = 987654321;    //초기 도착시간 매우 큰수로 초기화 해놓음.
}
 
void A_Check()
{
    for (int i = 0; i < a.size(); i++)
        if (a[i].second != EMPTY) {                        //창구 빈게 아니라면
            a[i].first.first--;                            //시간 경과하게 해줌(남은시간 감소)
            if (a[i].first.first == 0) {                //처리가 끝났다면
                b_wait.push(a[i].second);                //b대기열로 보내줌
                a[i].first.first = a[i].first.second;    //남은시간 = 창구처리시간 으로 초기화
                a[i].second = EMPTY;                    //이용고객 없다고 비워줌
            }
        }
    for (int i = 0; i < a.size(); i++)
        if (a[i].second == EMPTY &&                //만약 비어있고
            !a_wait.empty()) {                    //A대기열에 사람이 있으면
            a_number++;                            //접수창구 이용한 손님수 +1
            a[i].second = a_wait.front();        //접수창구 대기열중 제일 앞사람 넣어주고
            a_wait.pop();                        //대기열에서 삭제
            if (i == A - 1)                        //(A-1해준이유는 벡터는 0부터 시작하기 때문임)
                a_use.push_back(a[i].second);    //만약 분실한 지갑이 있던 창구라면 a_use에 밀어넣어줌
        }
}
 
void B_Check()
{
    for (int i = 0; i < b.size(); i++)
        if (b[i].second != EMPTY) {                        //현재 창구 이용중이면
            b[i].first.first--;                            //시간 경과(남은시간감소)
            if (b[i].first.first == 0) {                //0이되면 처리 끝난것
                b[i].first.first = b[i].first.second;    //남은시간=창구처리시간 으로 초기화
                b[i].second = EMPTY;                    //이용고객 없다고 비워줌
            }
        }
    for (int i = 0; i < b.size(); i++)
        if (b[i].second==EMPTY&&                //현재 창구 비어있고
            !b_wait.empty()) {                    //B대기열에 사람이 있다면
            b_number++;                            //정비창구 이용한 손님 +1
            b[i].second = b_wait.front();        //정비창구 대기열중 제일 앞사람 넣어주고
            b_wait.pop();                        //대기열에서 삭제
            if (i == B - 1)                        //(B-1해준이유는 벡터는 0부터 시작하기 때문임)
                b_use.push_back(b[i].second);    //만약 분실한 지갑이 있던 창구라면 b_use에 밀어넣어줌
        }
}
 
void solve()
{
    int index = 1;
                                            //a창구 b창구 이용한손님==K이면 모든 이용고객 끝. 
    while (!(a_number==K&&b_number==K)) {    //따라서 이용고객이 남았을때 돌릴것
        for (int i = index; i <= K; i++) {    //
            if (customer[i] == cur_time) {    //고객도착시간==현재시간 이면
                a_wait.push(i);                //접수창구 대기열에 넣어주고
                index = i + 1;                //index증가(다음손님으로)
            }
            else
                break;
        }
        A_Check();    //A창구 처리
        B_Check();    //B창구 처리
        cur_time++;    //현재시간 증가
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int test_case = 1; test_case <= T; test_case++) {
        /*초기화, 입력*/
        Answer = 0;
        cur_time = 0;
        a_number = 0;
        b_number = 0;
        cin >> N >> M >> K >> A >> B;
        Init();
        a.clear();
        b.clear();
        a_use.clear();
        b_use.clear();
        int tmp;
        for (int i = 0; i < N; i++) {
            cin >> tmp;
            a.push_back(make_pair(make_pair(tmp, tmp), EMPTY));
        }
        for (int i = 0; i < M; i++) {
            cin >> tmp;
            b.push_back(make_pair(make_pair(tmp, tmp), EMPTY));
        }
        for (int i = 1; i <= K; i++)
            cin >> customer[i];
        solve();                    //solve함수 호출
        for (int i = 0; i < a_use.size(); i++)
            for (int j = 0; j < b_use.size(); j++)
                if (a_use[i] == b_use[j])
                    Answer += a_use[i];    //같은 접수창구A와 같은 정비창구B를 이용했다면
        if (Answer == 0)
            Answer = -1;        //못찾으면 -1
        cout << "#" << test_case << " " << Answer << endl;    //정답출력
    }
 
    return 0;
}