2477 차량 정비소

#include <stdio.h>
#include <string.h>
#include <deque>
#include <vector>
 
using namespace std;
 
int num_account, num_repair, num_customer, find_acc, find_rep;
int time_acc[30], time_rep[30], time_arrive[1001];
int cur_acc[30], cur_rep[30];
int time_left_acc[30], time_left_rep[30];
int cur_acc_num, cur_rep_num;
int left_customer;
int dead = 1000000000;
deque<int> wait_list;
deque<int> wait_list2;
vector<vector<int> > record_acc;
vector<vector<int> > record_rep;
 
void new_testcase();
void time_pass(int time);
void accounting();
void repairing();
int find_customer(int idx1, int idx2);
int ending();
 
int main() {
    int test;
    scanf("%d", &test);
 
    for (int t = 1; t <= test; t++) {
        new_testcase();
 
        for (int i = 0; ; i++) {
            time_pass(i);
            accounting();
            repairing();
 
            if (ending()) {
                break;
            }
        }
        int num = find_customer(find_acc, find_rep);
        printf("#%d %d\n", t, num);
    }
}
 
int find_customer(int idx1, int idx2) {
    int rst_v = 0;
    vector<int> tmp_customer(num_customer + 1, 0);
    for (int i = 0; i < record_acc[idx1].size(); i++) {
        int cust = record_acc[idx1][i];
        tmp_customer[cust]++;
    }
    for (int i = 0; i < record_rep[idx2].size(); i++) {
        int cust = record_rep[idx2][i];
        tmp_customer[cust]++;
    }
 
    for (int i = 1; i <= num_customer; i++) {
        if (tmp_customer[i] > 1) {
            rst_v += i;
        }
    }
    if (rst_v > 0)
        return rst_v;
    else
        return -1;
}
 
int ending() {
    if (wait_list.size() > 0 || wait_list2.size() > 0)
        return 0;
    if (cur_acc_num > 0 || cur_rep_num > 0)
        return 0;
    if (left_customer > 0)
        return 0;
    return 1;
}
 
void time_pass(int time) {
    // waiting acc 생성
    for (int i = 1; i <= num_customer; i++)
        if (time >= time_arrive[i] && time_arrive[i] != dead) {
            wait_list.push_back(i);
            time_arrive[i] = dead;
            left_customer--;
        }
 
    // account 갱신 + waiting_rep 생성
    for (int i = 1; i <= num_account; i++) {
        if (time_left_acc[i] > 0) {
            time_left_acc[i]--;
 
            if (time_left_acc[i] == 0) {
                int tmp = record_acc[i].back();
                wait_list2.push_back(tmp);
 
                cur_acc[i] = 0;
                cur_acc_num--;
            }
        }
    }
 
    // repair 갱신
    for (int i = 1; i <= num_repair; i++) {
        if (time_left_rep[i] > 0) {
            time_left_rep[i]--;
 
            if (time_left_rep[i] == 0) {
                cur_rep[i] = 0;
                cur_rep_num--;
            }
        }
    }
}
 
void accounting() {
    if (wait_list.size() == 0)
        return;
 
    // waiting -> accounting 흐름
    while ((cur_acc_num < num_account) && (wait_list.size() > 0)) {
        for (int i = 1; i <= num_account; i++) {
            if (cur_acc[i] == 0) {
                int tmp = wait_list.front();
                wait_list.pop_front();
                record_acc[i].push_back(tmp);
 
                cur_acc[i] = 1;
                time_left_acc[i] = time_acc[i];
                cur_acc_num++;
            }
 
            if (wait_list.size() <= 0)
                break;
        }
    }
}
 
void repairing() {
    if (wait_list2.size() == 0)
        return;
 
    // waiting2 -> repairing 흐름
    while ((cur_rep_num < num_repair) && (wait_list2.size() > 0)) {
        for (int i = 1; i <= num_repair; i++) {
            if (cur_rep[i] == 0) {
                int tmp = wait_list2.front();
                wait_list2.pop_front();
                record_rep[i].push_back(tmp);
 
                cur_rep[i] = 1;
                time_left_rep[i] = time_rep[i];
                cur_rep_num++;
            }
 
            if (wait_list2.size() <= 0)
                break;
        }
    }
}
 
void new_testcase() {
    // vector
    record_acc.assign(30, vector<int>());
    record_rep.assign(30, vector<int>());
 
    // memset
    memset(time_acc, 0, sizeof(time_acc));
    memset(time_rep, 0, sizeof(time_rep));
    memset(time_arrive, 0, sizeof(time_arrive));
    memset(cur_acc, 0, sizeof(cur_acc));
    memset(cur_rep, 0, sizeof(cur_rep));
    memset(time_left_rep, 0, sizeof(time_left_rep));
    memset(time_left_acc, 0, sizeof(time_left_acc));
 
    // deque
    while (!wait_list.empty())
        wait_list.pop_back();
    while (!wait_list2.empty())
        wait_list2.pop_back();
 
    // variables
    cur_acc_num = 0;
    cur_rep_num = 0;
 
    // scanf
    scanf("%d %d %d %d %d", &num_account, &num_repair,
        &num_customer, &find_acc, &find_rep);
    left_customer = num_customer;
    for (int i = 1; i <= num_account; i++)
        scanf("%d", &time_acc[i]);
    for (int i = 1; i <= num_repair; i++)
        scanf("%d", &time_rep[i]);
    for (int i = 1; i <= num_customer; i++)
        scanf("%d", &time_arrive[i]);
}
 

체감상 정말 생각할게 많았던 문제였다

코드 길이만 봐도 200줄 가까이 되네

그래도 뭐 dfs 같은 알고리즘이 전혀 필요 없고,

그냥 덱이랑 벡터를 적절하게 사용할 줄 알면 됐다

거기에다가 중간중간에 세밀한 사고 과정이 필요해서 애를 좀 먹었다