2477.차량 정비소

오랜만에 문제를 풀었다. 그 동안 했던 것 중에 잘 모르겠던거 복습도하고 충분한 휴식도 취하고 왔다. 이제 다시 달려야지!!

이번에 풀어볼 문제는 SW Expert의 2477번 문제 차량 정비소이다.

SW Expert Academy

생각보다 굉장히 까다로운 시뮬레이션이고 이 문제는 설계를 망치면 그냥 꼬여버리는 문제이다.

설계만 잘한다면 난이도는 그리 높지 않다. 그럼에도 1시간 29분 정도 걸렸다. 너무 헷갈려..ㅠ

 

이 문제를 푸는 포인트는 생각해보면 굉장히 간단하다. 

1. 대기열을 생각해줘야한다.

 => 바로 고객이 도착해서 접수 창구로 가는 사이에 waiting하는 대기열

 => 접수창구에서 정비창구로가는 waiting 대기열을 생각해주고 설계히면 된다.

 

2. 둘다 들리는 경우를 체크해주면된다.

=> 배열을 하나 선언해서 A와 B 창구를 들린 고객번호의 index의 값 더해 2가 나오면 둘 다 거쳐간 것으로 체크하였다.

 

 

---

 

< Code 설명 >

#pragma warning(disable:4996)
#include <iostream>
#include <deque>
#include <string.h>
 
#define MAX 1001
 
using namespace std;
 
int T, N, M, K, A, B;
 
int answer[MAX]; // 접수창구와 정비창구를 거쳤는지 판별하는 배열
 
deque<pair<int, int>>cus; // 고객정보 : 고객번호, 걸린시간
 
deque<int>wait1; // 대기 큐 ( 도착에서 접수창구 )
deque<int>wait2; // 대기 큐 ( 접수창구에서 정비창구 )
 
deque<pair<int,int>>box1; // 고객번호, 소요 시간 => 고객번호가 0이면 고객을 받음 소요시간이 0이면 두 번째 대기큐로 보냄
deque<pair<int,int>>box2; // 고객번호, 소요 시간 
 
deque<int> box1_save; // 접수창구 소요시간 저장
deque<int> box2_save; // 정비창구 소요시간 저장
 
int ans; // 접수창구와 정비창구를 거친 고객번호 : 정답
 
void search(){
    int cnt = 0;
    while (true){
        if (cnt == K) // 고객 수가 전부다 업무가 끝나면
            break;// 종료
 
    
        for (int i = 0; i < (int)cus.size(); i++){ // 고객이 도착한 경우 대기 큐에 저장
            if (cus.front().second == 0){ // 고객이 도착한경우
                wait1.push_back(cus.front().first); // 해당 고객을 첫 번째 대기큐에 저장
                if (!cus.empty()){ // 고객정보가 비어있지 않았다면
                    cus.pop_front(); // 도착한 고객정보 제거
                    i = -1; // 제거 후에는 다시 제일 처음부터 탐색함 ( 도착한 고객이 또 있을 수 있으니 )
                }
            }
        }
        
 
        for (int i = 0; i < N; i++){ // 접수 창구 수만큼 탐색
            if (box1[i].second == 0){ // 접수창구 소요시간이 다지나면
                box1[i].second = box1_save[i]; // 접수창수 소요시간 다시 초기화
 
                if (i + 1 == A) // 우리가 찾는 창구를 이용한 고객이라면
                    answer[box1[i].first] += 1; // 방문 고객 idx값 +1
 
                wait2.push_back(box1[i].first); // 접수창고에서 업무 다봤으니 두 번째 대기큐에 저장
                box1[i].first = 0; // 대기 큐로 보냈으니 접수창구에서는 이용고객 제거
            }
 
            if (box1[i].first == 0 && !wait1.empty()){ // 접수창구가 비어있으면 
                box1[i].first = wait1.front(); // 접수창구에 대기 큐 제일 앞의 값을 저장    
                if (!wait1.empty())
                    wait1.pop_front(); // 대기 큐의 제일 앞은 삭제
            }
 
            if (box1[i].first) // 접수창구에 고객이 있으면
                box1[i].second -= 1; // 소요시간 -1
        }
 
        
        for (int i = 0; i < M; i++){ // 정비 창구의 수만큼 탐색
            if (box2[i].second == 0){ // 정비창구 소요시간이 다지나면
                box2[i].second = box2_save[i]; // 정비창수 소요시간 다시 초기화
 
                if (i + 1 == B && answer[box2[i].first]==1) // 이전에 A창구를 들렸으면서 B창구를 들린 고객이라면
                    answer[box2[i].first] += 1; // 방문 고객 idx값 +1
                
 
                box2[i].first = 0; // 접수창구 이용고객 제거
                cnt += 1; // 고객한명이 완전히 업무를 마치고 나갔으므로 +1
            }
 
            if (box2[i].first == 0 && !wait2.empty()){ // 정비창구가 비어있으면 
                box2[i].first = wait2.front(); // 정비창구에 대기 큐 제일 앞의 값을 저장    
                wait2.pop_front(); // 대기 큐의 제일 앞은 삭제
            }
 
            if (box2[i].first) // 정비창구에 고객이 있으면
                box2[i].second -= 1; // 소요시간 -1
        }
 
        for (int i = 0; i < (int)cus.size(); i++) // 시간이 지났으므로
            cus[i].second -= 1;  // 고객 도착시간 - 1
    }
    
    for (int i = 1; i <= K; i++){ // A와 B 창구를 거친 고객 idx는 2가 되어있으므로
        if (answer[i]==2) // 결과가 2인 배열값만 더해줌
            ans += i;
    }
}
 
void init(){ // 초기화
    memset(answer, 0, sizeof(answer));
    ans = 0;
    cus.clear();
    wait1.clear();
    wait2.clear();
    box1.clear();
    box2.clear();
    box1_save.clear();
    box2_save.clear();
}
 
int main() {
    freopen("2477.txt", "r", stdin);
    cin >> T;
    for (int z = 1; z <= T; z++){
        init();
        cin >> N >> M >> K >> A >> B;
        int tmp;
        for (int i = 0; i < N; i++){
            cin >> tmp;
            box1.push_back(make_pair(0,tmp));
            box1_save.push_back(tmp);
        }
    
        for (int i = 0; i < M; i++){
            cin >> tmp;
            box2.push_back(make_pair(0,tmp));
            box2_save.push_back(tmp);
        }
 
        for (int i = 1; i <= K; i++){
            cin >> tmp;
            cus.push_back(make_pair(i, tmp));
        }
 
        search();
        if (ans == 0) // 더해지지 않았다는 것은 우리가 찾는 A,B를 모두 거친 고객이 없다는 것이므로
            cout << "#" << z << " " << -1 << "\n"; // -1을 출력
        else
            cout << "#" << z << " " << ans << "\n";// 있다면 결과 출력
    }
    return 0;
}