[모의 SW 역량테스트] 차량 정비소

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy

SW Expert Academy

풀이

* 시간 0부터 들어온 고객을 접수 창구에 배정한다. 이 때, 접수 창구가 꽉 차서 배정되지 못한 고객은 대기 배열에 넣는다. (waitA)

* USER <= idx(고객 번호) / rec(배정된 접수 창구 번호) / rep (배정된 정비 창구 번호) / time(경과된 시간) / wait(접수를 마치고 대기한 시간) 

* 큐를 두 개 사용한다. (접수 : aq / 정비 : bq) 

 

* bfs()의 flow 

1) inputWaitingA() : 접수 대기열에 있는 사람들을 접수 창구에 넣음 / 지금 들어온 사람들을 접수 대기열에 넣는다. 

2) 접수 창구 처리 => 완료하면 정비 창구 대기열에 넣는다. 

3) inputWaitingB() : 정비 창구 대기열에 잇는 사람들을 정비 창구에 넣는다. 

*** 정비 창구가 꽉 차서 들어가지 못한 사람들은 wait를 1씩 증가시켜준다. (wait가 클 수록 더 빨리 창구에 배치시키고, 만약 wait가 같다면 접수 창구 번호가 적은 순으로 배치한다.)

① 먼저 기다리는 고객이 우선한다.

② 두 명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 정비 창구로 이동한 경우, 이용했던 접수 창구번호가 작은 고객이 우선한다.

③ 빈 창구가 여러 곳인 경우 정비 창구번호가 작은 곳으로 간다.

 

 

* 접수 창구 번호가 a / 정비 창구 번호가 b인 사람들의 고객번호를 더한다. 

 

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227

#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cstring> using namespace std; //차량정비소 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy   int n, m, k, a, b, ans = 0; int A[10], B[10], T[1001]; typedef struct User {     int idx, rec, rep, time, wait;     bool chk;     User(int i, int rc, int rp, int t, int w, bool c) : idx(i), rec(rc), rep(rp), time(t), wait(w), chk(c){}; } User; bool chkA[10], chkB[10], finished[1001]; vector<User> waitA, waitB; queue<User> aq, bq;   bool compare(const User &a, const User &b) {     if (a.wait == b.wait)     {         return a.rec < b.rec;     }     return a.wait > b.wait; } bool check() {     for (int i = 1; i <= k; i++)     {         if (!finished[i])             return false;     }     return true; } void inputWaitingB() {     //정비 큐 만들기     //wait의 값이 같다면 접수 창구의 번호가 작은 순으로 정렬하낟.       if (waitB.size() > 0)     {         sort(waitB.begin(), waitB.end(), compare);         //이전에 대기하던 사람이 있었다면         for (int j = 1; j <= m; j++)         {             //정비 창구에 남는 곳이 있는지 확인한다.             if (!chkB[j])             {                 chkB[j] = true;                 if (waitB[0].rec == a && j == b)                 {                     ans += waitB[0].idx;                 }                 bq.push(User(waitB[0].idx, waitB[0].rec, j, waitB[0].time + 1, waitB[0].wait, waitB[0].chk));                 waitB.erase(waitB.begin());                 if (!waitB.size())                     break;             }         }           if (waitB.size() > 0)         {             //wiat를 하나씩 늘려준다.             for (int j = 0; j < waitB.size(); j++)             {                 waitB[j].wait += 1;             }         }     } } void inputWaitingA(int hour) {     if (waitA.size() > 0)     {         //이미 대기중인 사람들을 먼저 넣는다.         for (int j = 1; j <= n; j++)         {             if (!chkA[j])             {                 //비어있는 접수대                 chkA[j] = true;                 aq.push(User(waitA[0].idx, j, 0, 1, 0, true));                 waitA.erase(waitA.begin());                 if (!waitA.size())                     break;             }         }     }     for (int i = 1; i <= k; i++)     {           if (T[i] == hour)         {             bool chk = false;             for (int j = 1; j <= n; j++)             {                 if (!chkA[j])                 {                     chkA[j] = true;                     aq.push(User(i, j, 0, 1, 0, true));                     chk = true;                     break;                 }             }             if (!chk)                 waitA.push_back(User(i, 0, 0, 0, 0, false));         }     } } void bfs() {     /*     접수 창구의 우선순위는 아래와 같다.      ① 여러 고객이 기다리고 있는 경우 고객번호가 낮은 순서대로 우선 접수한다.    ② 빈 창구가 여러 곳인 경우 접수 창구번호가 작은 곳으로 간다.     정비 창구의 우선순위는 아래와 같다.      ① 먼저 기다리는 고객이 우선한다.    ② 두 명 이상의 고객들이 접수 창구에서 동시에 접수를 완료하고 정비 창구로 이동한 경우, 이용했던 접수 창구번호가 작은 고객이 우선한다.    ③ 빈 창구가 여러 곳인 경우 정비 창구번호가 작은 곳으로 간다.       */     int hour = 0;     while (1)     {         if (check())         {             //모두 다 할 일을 끝냈는지 확인한다.             break;         }           inputWaitingA(hour);         //접수 진행         ++hour;         int size = aq.size();           while (size--)         {             //접수 진행             //접수가 다 끝나면 바로 waiting에 넣어버린다.             User now = aq.front();             aq.pop();               // cout << now.idx << " " << now.rec << " " << now.time << "\n";             if (now.time == A[now.rec])             {                 //끝마쳤음                 chkA[now.rec] = false;                 waitB.push_back(now);             }             else             {                 aq.push(User(now.idx, now.rec, now.rep, now.time + 1, now.wait, now.chk));             }         }           inputWaitingB();           size = bq.size();         while (size--)         {             //정비 진행             User now = bq.front();             bq.pop();               if (now.time == A[now.rec] + B[now.rep])             {                 chkB[now.rep] = false;                 finished[now.idx] = true;             }             else             {                 bq.push(User(now.idx, now.rec, now.rep, now.time + 1, now.wait, now.chk));             }         }     } } void init() {     memset(finished, 0, sizeof(finished));     memset(chkA, 0, sizeof(chkA));     memset(chkB, 0, sizeof(chkB));     waitB.clear();     waitA.clear();     ans = 0; } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       int t;     cin >> t;       for (int tc = 1; tc <= t; tc++)     {         init();         cin >> n >> m >> k >> a >> b;           for (int i = 1; i <= n; i++)         {             cin >> A[i];         }         for (int i = 1; i <= m; i++)         {             cin >> B[i];         }         for (int i = 1; i <= k; i++)         {             cin >> T[i];         }           bfs();         if (!ans)             ans = -1;           cout << "#" << tc << " " << ans << '\n';     }     return 0; }