[ SWEA 2477 ] 차량 정비소 (C++)

SWExpertAcademy의 차량 정비소(2477) 문제이다.

[ 문제풀이 ]

1) 문제가 많이 길다.. 문제를 간단하게 정리한 후에 시작해보자.

   차량정비소에는 '접수창구'와 '정비창구'가 있다. 접수창구는 접수창구만의 우선순위 규칙을 통해서 손님을 접수하고,

   정비창구는 정비창구만의 우선순위 규칙을 통해서 손님을 골라서 정비를 하게 된다.

   반드시, 접수창구에서 접수를 받은 후에 정비창구로 갈 수 있다.

   이 때, 접수창구를 A번을 이용하고, 정비창구를 B번을 이용한 손님의 번호의 총 합을 구하면 된다.

  

   문제 풀이에 들어가기 전에, 먼저 본인이 문제를 해결하기 위해서 선언한 구조체와 변수들에 대해서 설명 후에 문제 풀이에

   들어가 보자.

   본인은 구조체를 3개를 만들어 주었다. '고객'에 대한 구조체, '접수창구'에 대한 구조체, '정비창구'에 대한 구조체.

   각각의 구조체에서 관리하는 변수들은 다음과 같다.

struct CUSTOMER           

{                            
    int  Num;                   

int ArriveTime;               

int RepairDesk;           

int ReceptionDesk;

int Start_Reception;            

int Finish_Reception;    

int Start_Repair;         

int Finish_Repair;            

bool Finish;                

}                        

struct REPAIR

{

bool Use;

int RepairTime;

}

struct RECEPTION

{

bool Use;

int ReceptionTime;

}

  위와 같이 3개의 구조체를 사용해 주었다. 먼저 구조체에 들어있는 변수들이 의미하는 것 부터 알아보자. 

   먼저 REPAIR 구조체와 RECEPTION 구조체를 보자.

   bool형 변수인 'Use'는 현재 해당 접수 / 정비 창구를 사용하고 있는 사람이 있는지 없는지를 체크해주는 변수이다.

   누군가가 사용하고 있다면 Use = true, 그게 아니라면 Use = false로 설정해 주었다.

   RepairTime , ReceptionTime 은 각각의 접수 / 정비 창구가 일을 처리하는데 걸리는 시간을 저장해 주었다.

   본인은 이 구조체를 자료형으로 갖는 구조체 배열을 선언해 주었다.

   두 번째로, CUSTOMER 구조체이다.

   int Num 은 고객의 번호를 저장해 주는 변수이다.

   int ArriveTime은 고객이 차량 정비소에 도착했을 때의 시간이다. 이 시간은 입력으로 주어지는 값이기도 하며,

   이 시간을 통해서 접수창고에 가야될 시간인지 아닌지를 판단해 준다.

   int RepairDesk , int ReceptionDesk 는 해당 고객이 사용한 접수 / 정비 창구의 번호를 저장해 주는 변수이다.

   최종적으로, 방문한 고객들을 모두 탐색하면서 이 변수의 값을 확인해서 정답을 도출해 낸다.

   int Start_Reception , int Finish_Reception , int Start_Repair, int Finish_Repair

   이 변수들은 고객이 접수 / 정비 창구에서 일을 처리하는 시작시간과 종료시간을 나타낸다.

   위에서 말한, ArriveTime을 통해서 'Start_Reception' 즉, 접수 창구에 들어가는 시간을 계산할 수 있고

   접수 창구에 들어가는 순간, 접수창구에서 처리를 끝내고 나오는 시간을 알 수 있고, 그 시간을 통해서

   정비창구에 들어가는 시간을 알 수 있다. 정비창구에 들어가는 시간을 알게 되면, 정비창구에서 처리를 끝내는 시간을

   알 수 있고, 이 끝내는 시간을 통해서 가장 마지막 변수인 'Finish'를 true로 체크해줄 수 있다.

   Finish변수는 고객이 접수 , 정비창구에서 모든 일을 처리해서 끝난 상태인지 아닌지를 체크해주는 변수이다.

2) 그렇다면 이제 이 구조체와 이 변수들을 이용해서 어떻게 구현을 했는지 알아보자.

   문제의 전체적인 순서를 보자면 다음과 같이 정리해볼 수 있다.

   1. 차량 정비소에 도착하는 사람이 있는지 판단.

   2. 접수창구에 들어갈 사람이 있는지, 있다면 접수를 할 수 있는 상황인지 판단.

      - 만약 접수를 할 수 없다면, 대기줄에 줄을 서야한다.

   3. 정비창구에 들어갈 사람이 있는지, 있다면 정비를 할 수 있는 상황인지 판단.

      - 만약 정비를 할 수 없다면, 대기줄에 줄을 서야한다.

  

   위의 3가지 과정을 계속해서 무한반복 하면 된다. 그럼 종료는 ? 바로 모든 사람들이 모든 업무를 끝냈을 때 위의 과정을

   반복하는 것을 종료하면 된다. 그걸 어떻게 알지 ? 위에서 말했듯이, CUSTOMER 구조체에는 'Finish'라는 변수를 만들어

   놓았고, 모든 고객의 Finish변수가 true이면 모든 사람이 업무를 끝냈다는 것을 알 수 있다.

   그럼 위의 3가지 과정을 순차적으로 알아보자.

   1. 차량정비소에 도착하는 사람이 있는지 판단.

    - 입력으로 차량정비소에 도착하는 사람 순서로 시간이 주어진다.

      예를 들어서 현재 0초이고, 차량정비소에 0초에 도착하는 사람이 있다면, 이 사람은 0초에 접수창구에서 접수를 하거나

      접수창구에 줄을 서거나 둘 중 하나를 하게 된다.

      즉, 입력으로 주어지는 고객의 도착 시간을 이용해서 현재 시간에 차량 정비소에 도착하는 사람이 있는지 없는지

      판단할 수 있다.

   2. 접수창구에 들어갈 사람이 있는지, 있다면 접수를 할 수 있는 상황인지 판단

    - 1번 과정에서 우리는 차량정비소에 도착하는 사람이 있는지 없는지를 판단해 주었다. 없을때는 뭐 처리해줘야 할 일이

      없으니 있다고 가정해보자. "차량정비소에 도착하는 사람이 있다" 라는 것은 "접수창구에서 접수를 받을 수 있는지

      없는지 판단해볼 필요가 있다" 라는 말이다.

      그래서 본인은 현재 접수를 할 수 있는, 현재 일을 하고 있지 않은 접수 창구의 갯수를 받아오는 함수를 하나 만들어

      주었다. 만약, 사용할 수 있는 접수 창구가 존재한다면 바로 도착하는 사람을 접수창구에 넣어주면 될까??

      아니다. 왜냐하면 기존에 대기열이 있을 수도 있기 때문이다. 이미 접수를 받기 위해서 기다리고 있는 사람이 5명이

      있는데, 내가 지금 도착했고 지금 접수창구에 자리가 났다고 내가 들어갈 수 있는 것은 아니다. 저 5명 뒤에 줄을 서야

      한다.

      이 부분을 위해서 본인은 "대기열"의 역할을 하는 큐를 2개 만들어주었다.(Reception 1개, Repair 1개)

      먼저 접수창구에서 대기열의 역할을 하는 큐를 사용하는 법은 다음과 같다.

      1. 손님이 차량정비소에 도착하면 일단 무조건 접수창구의 대기열에 넣어준다.

      2. 현재 사용할 수 있는지 접수 창구가 있다면, 앞에서 부터 한명씩 차례대로 접수 창구에 넣어준다.

       이렇게 되면 위에서 말한, 줄을 서야 하는 경우 또한 자연스럽게 처리할 수 있다.

       예를 들어보자. 접수창구가 1개이고, 일을 처리하는데 2초가 걸린다. 0초에 A, B 2명의 사람이 왔고 1초에 C 1명의 사람

       이 왔다고 생각해보자.

       0초에 A, B가 도착하는 순간 접수창구 대기열 큐에는 { A, B } 로 들어가게 된다.

       0초에 사용할 수 있는 접수창구가 존재하므로 앞에서 부터 하나씩 빼면 큐에는 { B } 가 남게 된다.

       1초에 C가 도착한다. 도착하는 순간 접수창구 대기열 큐에 넣어준다. 즉, 큐는 { B, C } 와 같은 형태가 된다.

       2초에 접수창구에 자리가 생기고 큐에서 하나씩 빼서 넣어주면 B가 빠지고 { C }  만 남게 된다.

       이런식으로 사용해주었다.

    3. 정비창구에 들어갈 사람이 있는지, 있다면 정비를 할 수 있는 상황인지 판단

     - 사실 이부분은 위에서 말한 접수창구의 처리 방법과 거의 유사하다. 그렇다면, 접수창구에서는 "차량정비소에 오는

       사람을 일단 무조건 접수창구 대기열 큐에 넣었다" 고 했는데, 정비창구에서는 어떻게 넣어줘야할까?

       "현재 시간에 정비창구에 들어와야 할 사람"을 넣어주었다. 현재 시간에 특정 고객이 정비창구를 이용해야 하는지

       안하는지를 어떻게 알 수 있을까 ? CUSTOMER 구조체에서 이런 변수들이 있었다.

       Start_Reception, Finish_Reception, Start_Repair, Finish_Repair

       2번 과정에서 접수를 시작하는 순간의 시작을, Start_Reception에 저장, 그 Start_Reception 값에 따라서

       자연스럽게 Finish_Reception의 시간 또한 알 수 있었고, 이 시간으로 Start_Repair 의 시간까지 알 수 있다.

       즉, 접수창구에 들어가서 접수를 받는 순간, 우리는 정비창구에 들어갈 시간 까지 알 수 있게 된다.

       역시나 물론 그 시간에 무조건 정비창구에 들어가면 안된다. 왜 ? 대기열이 있을 수도 있으니까 !

       그런데 주의해야 할 점이, 접수창구와 정비창구에서 우선순위를 뽑는 기준이 다르다.

       먼저 우선순위를 뽑는 공통점은 "먼저 기다리는 사람이 먼저 들어간다"이다. 이건 뭐 당연한 말이다.

       그런데 접수창구의 경우, 여러 고객이 동시에 올 경우, 즉, 0초에 2명이 같이 차량정비소에 도착하는 경우이다.

       이 때는, 고객번호가 낮을수록 높은 우선순위를 갖게된다.

       하지만, 정비창구의 경우는 다르다. 2명 이상의 고객이 동시에 접수를 종료하고 정비창구로 향하게 된다면,

       접수 창구번호가 작은 고객이 더 높은 우선순위를 갖는다.

       말을 다시 정리를 해보자.

       접수창구에서 "차량 정비소에 도착하는 사람을 일단 무조건 접수창구의 대기열 큐에 넣어준다" 라는 것과

       같은 개념으로, "접수가 끝나는 시간인 사람들은 일단 무조건 정비창구의 대기열 큐에 넣어준다" 를 해줘야 하는데

       이 때, 대기열 큐에 마음대로 넣는것이 아니라, 더 작은 접수창구를 이용한 손님이 먼저 들어가도록 넣어주면

       되는 것이다.

   이렇게 위의 3가지 과정을 계속해서 반복하면 된다. 물론, 저 중간중간에 손님들의 상태 및 접수 / 정비창구들의

   상태를 바꿔줘야 하는 부분도 있지만 그런 부분들은 코드를 통해서 확인해보도록 하자.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
 
#define endl "\n"
#define CUSTOM_MAX 1001
#define MAX 10
using namespace std;
 
struct CUSTOMER                // 고객을 관리하는 구조체
{
    int Num;                // 고객의 번호
    int ArriveTime;            // 고객이 '차량정비소에 도착하는 시간'
    int RepairDesk;            // 고객이 이용한 '정비창구의 번호'
    int ReceptionDesk;        // 고객이 이용한 '접수창구의 번호'
    int Start_Reception;    // 고객이 '접수창구를 이용하기 시작한 시간'
    int Finish_Reception;    // 고객이 '접수창구 이용을 끝내는 시간'
    int Start_Repair;        // 고객이 '정비창구를 이용하기 시작한 시간'
    int Finish_Repair;        // 고객이 '정비창구 이용을 끝내는 시간'
    bool Finish;            // 고객이 모든업무를 끝냈는지 판단하는 변수.
};
 
struct REPAIR
{
    bool Use;
    int RepairTime;
};
 
struct RECEPTION
{
    bool Use;
    int ReceptTime;
};
 
int N, M, K ,A, B, Answer;
CUSTOMER Custom[CUSTOM_MAX];        // 고객 구조체 배열
REPAIR RepairDesk[MAX];                // 정비창구 구조체 배열
RECEPTION ReceptionDesk[MAX];        // 접수창구 구조체 배열
queue<int> Reception_Waiting, Repair_Waiting;    // 대기열의 역할을 하는, 큐 2개.
 
void Initialize()
{
    Answer = 0;
    while (Reception_Waiting.empty() == 0) Reception_Waiting.pop();
    while (Repair_Waiting.empty() == 0) Repair_Waiting.pop();
}
 
void Input()
{
    cin >> N >> M >> K >> A >> B;
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        ReceptionDesk[i].ReceptTime = a;
        ReceptionDesk[i].Use = false;
    }
    for (int i = 1; i <= M; i++)
    {
        int a; cin >> a;
        RepairDesk[i].RepairTime = a;
        RepairDesk[i].Use = false;
    }
    for (int i = 1; i <= K; i++)
    {
        int a; cin >> a;
        Custom[i].Num = i;
        Custom[i].ArriveTime = a;        // 입력과 동시에, 고객이 도착하는 시간을 알 수 있다.
        Custom[i].ReceptionDesk = -1;
        Custom[i].RepairDesk = -1;
        Custom[i].Finish = false;
        Custom[i].Start_Reception = Custom[i].Start_Repair = -1;
        Custom[i].Finish_Reception = Custom[i].Finish_Repair = -1;
    }
}
 
bool Reception_Standard(int x, int y)
{
    if (Custom[x].Num < Custom[y].Num) return true;
    return false;
}
 
bool Repair_Standard(int x, int y)
{
    if (Custom[x].ReceptionDesk < Custom[y].ReceptionDesk) return true;
    return false;
}
 
void Arrive(int Time, string S)
{
    vector<int> V;
    if (S == "Reception")        // 접수창구의 경우
    {
        for (int i = 1; i <= K; i++)
        {
            /* 일단 현재 Time 초에 도착하는 사람이 있으면 무조건 
               접수창구 대기열에 넣어준다.
            */
            if (Custom[i].ArriveTime == Time)
            {
                V.push_back(i);
            }
        }
        sort(V.begin(), V.end(), Reception_Standard);    // 우선순위에 맞게 정렬 후 삽입.
        for (int i = 0; i < V.size(); i++) Reception_Waiting.push(V[i]);
    }
    else                        // 정비창구의 경우
    {
        for (int i = 1; i <= K; i++)
        {
            if (Custom[i].Start_Repair == Time)
            {
                V.push_back(i);
            }
        }
 
        sort(V.begin(), V.end(), Repair_Standard);
        for (int i = 0; i < V.size(); i++) Repair_Waiting.push(V[i]);
    }
}
 
void MakeFinish(int Time)
{
    /* 
    'Time'초에 접수 or 정비가 끝나는 사람이 있을 경우 체크해주는 함수
    사용한 접수 / 정비창구의 상태를 바꿔주어야 한다.
    정비 창구의 이용이 끝나게 되면, 그 사람은 모든 업무를 처리한 것이므로 Finish변수도 Check.
    */
    for (int i = 1; i <= K; i++)
    {
        if (Custom[i].Finish_Reception == Time)
        {
            ReceptionDesk[Custom[i].ReceptionDesk].Use = false;
        }
        if (Custom[i].Finish_Repair == Time)
        {
            RepairDesk[Custom[i].RepairDesk].Use = false;
            Custom[i].Finish = true;
        }
    }
}
 
bool Finish_Check(int Time)
{
    /* 모든 고객들이 모든 업무를 다 처리했는지 CHECK 하는 함수. */
    int Cnt = 0;
    for (int i = 1; i <= K; i++)
    {
        if (Custom[i].Finish == true) Cnt++;
    }
 
    if (Cnt == K) return true;
    return false;
}
 
int Receive_Num(string S)
{
    /* 현재 사용할 수 있는 접수 / 정비 창구의 갯수를 return 하는 함수. */
    int Cnt = 0;
    if (S == "Reception")
    {
        for (int i = 1; i <= N; i++)
        {
            if (ReceptionDesk[i].Use == false) Cnt++;
        }
    }
    else
    {
        for (int i = 1; i <= M; i++)
        {
            if (RepairDesk[i].Use == false) Cnt++;
        }
    }
    
    return Cnt;
}
 
void Service(int Time, int Idx, string S)
{
    if (S == "Reception")
    {
        for (int i = 1; i <= N; i++)
        {
            if (ReceptionDesk[i].Use == false)
            {
                ReceptionDesk[i].Use = true;
                Custom[Idx].ReceptionDesk = i;
                Custom[Idx].Start_Reception = Time;
                Custom[Idx].Finish_Reception = Time + ReceptionDesk[i].ReceptTime;
                Custom[Idx].Start_Repair = Custom[Idx].Finish_Reception;
                return;
            }
        }
    }
    else
    {
        for (int i = 1; i <= M; i++)
        {
            if (RepairDesk[i].Use == false)
            {
                RepairDesk[i].Use = true;
                Custom[Idx].RepairDesk = i;
                Custom[Idx].Start_Repair = Time;
                Custom[Idx].Finish_Repair = Time + RepairDesk[i].RepairTime;
                return;
            }
        }
    }
}
 
void Solution()
{
    // 전체 Process 과정.
    int Time = 0;
 
    while (1)
    {
        MakeFinish(Time);                                // 끝나는 것을 표시
        if (Finish_Check(Time) == true) break;            // while문 종료 조건.
        
        Arrive(Time, "Reception");                        // 도착을 표현한 함수.
        int Reception_Num = Receive_Num("Reception");    // 사용할 수 있는 접수창구 갯수 받아오기
        int Recept_Size = Reception_Waiting.size();        // 대기열 인원 수 받아오기
        if (Recept_Size != 0 && Reception_Num > 0)
        {
            while (Reception_Waiting.empty() == 0)        // 한 명씩 넣어준다.
            {
                if (Reception_Num == 0) break;
                Service(Time, Reception_Waiting.front(), "Reception");
                Reception_Waiting.pop();
                Reception_Num--;
            }
        }
 
        // 위와 똑같은 방식. 다만, 위에는 Reception, 지금부터는 Repair.
        Arrive(Time, "Repair");
        int Repair_Num = Receive_Num("Repair");
        int Repair_Size = Repair_Waiting.size();
        if (Repair_Size != 0 && Repair_Num > 0)
        {
            while (Repair_Waiting.empty() == 0)
            {
                if (Repair_Num == 0) break;
                Service(Time, Repair_Waiting.front(), "Repair");
                Repair_Waiting.pop();
                Repair_Num--;
            }
        }
        Time++;
    }
 
    for (int i = 1; i <= K; i++)
    {
        if (Custom[i].ReceptionDesk == A && Custom[i].RepairDesk == B)
        {
            Answer = Answer + i;
        }
    }
 
    if (Answer == 0) Answer = -1;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}