2477번 차량 정비소

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

엄청 어려웠다. 

이와 같은 유형(http://hsdevelopment.tistory.com/27)을 잘 못 풀겠다.

시간에 따라 어디를 이용하는 유형..

다른 분의 코드를 참고하였다.

#include <iostream>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
 
using namespace std;
 
int N = 0, M = 0, K = 0, A = 0, B = 0;
 
int a[10] = { 0, }; // 접수 창구가 고장을 접수하는 데 걸리는 시간
int a_time[10] = { 0, }; // 위와 같다
 
int b[10] = { 0, }; // 정비 창구가 차량을 정비하는 데 걸리는 시가
int b_time[10] = { 0, }; // 위와 같다
 
int arrive[1003] = { 0, }; // 고객이 차량 정비소를 방문하는 시간
 
int a_use[10] = { 0, }; 
// a_use[i] = i번 째 접수 창구를 이용하는 고객 번호
 
int b_use[10] = { 0, };
// b_use[i] = i번 째 정비 창구를 이용하는 고객 번호
 
bool check[1003] = { false, };
 
int result = 0;
 
queue<int> a_waiting; // 정수 창구로 가기 위한 대기열
queue<int> b_waiting; // 정비 창구로 가기 위한 대기열
 
void findNumber(int time, int cnt)
{
    if (cnt == K) return; // 완료
 
    // 시간 순서로 접수 창구로 가기 위한 대기열에 배치
    for (int i = 1; i <= K; i++)
    {
        if (time == arrive[i]) a_waiting.push(i);
        else if (time < arrive[i]) break;
    }
 
    // 접수 창구 배정
    for (int i = 1; i <= N; i++)
    {
        if (a_waiting.empty()) break;
 
        if (a_use[i] == -1) // i 번 째 접수 창구를 이용하는 사람이 없다면
        {
            if (i == A) check[a_waiting.front()] = true;
 
            a_use[i] = a_waiting.front();
            a_waiting.pop();
        }
    }
 
    // 정비 창구 배정
    for (int i = 1; i <= M; i++)
    {
        if (b_waiting.empty()) break;
 
        if (b_use[i] == -1) // i 번 째 정비 창구를 이용하는 사람이 없다면
        {
            if (i == B && check[b_waiting.front()]) result += b_waiting.front(); // not result += i;
 
            b_use[i] = b_waiting.front();
            
            b_waiting.pop();
            
            ++cnt; 
            // 접수 창구 코드에 쓰면 안 된다. 
            // 37번 째 코드 때문에 원하는 타이밍보다 더 빨리 탈출해버리기 때문이다 
        }
    }
 
    // 1초 경과 : 접수 창구
    for (int i = 1; i <= N; i++)
    {
        if (a_use[i] != -1)
        {
            --a_time[i]; // 1초 감소
 
            if (a_time[i] == 0)
            {
                a_time[i] = a[i];
                b_waiting.push(a_use[i]); // 접수 창구에서의 시간이 끝났으므로, 정비 창구 대기열로 배치
                a_use[i] = -1;
            }
        }
    }
 
    // 1초 경과 : 정비 창구
    for (int i = 1; i <= M; i++)
    {
        if (b_use[i] != -1)
        {
            --b_time[i];
 
            if (b_time[i] == 0)
            {
                b_time[i] = b[i];
                b_use[i] = -1;
            }
        }
    }
 
    findNumber(time + 1, cnt);
 
    return;
}
 
void init() // 초기화
{
    result = 0;
 
    while (!a_waiting.empty())
    {
        a_waiting.pop();
    }
 
    while (!b_waiting.empty())
    {
        b_waiting.pop();
    }
 
    memset(a_use, -1, sizeof(a_use));
    memset(b_use, -1, sizeof(b_use));
 
    memset(check, false, sizeof(check));
}
 
int main(void)
{
    int T = 0; // 테스트 케이스
 
    scanf("%d", &T);
 
    for (int tc = 1; tc <= T; tc++)
    {
        init();
 
        scanf("%d %d %d %d %d", &N, &M, &K, &A, &B);
 
        for (int i = 1; i <= N; i++)
        {
            // 접수 창구
            scanf("%d", &a[i]);
 
            a_time[i] = a[i];
        }
 
        for (int i = 1; i <= M; i++)
        {
            // 정비 창구
            scanf("%d", &b[i]);
 
            b_time[i] = b[i];
        }
 
        for (int i = 1; i <= K; i++)
        {
            // i번 째 고객이 도착한 시간
            scanf("%d", &arrive[i]);
        }
 
        findNumber(0, 0);
 
        printf("#%d %d\n", tc, result != 0 ? result : -1);
    }
 
    return 0;
}