✅ What I did today

• 프로그래머스

⚔️ 프로그래머스

상담원 인원

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>

using namespace std;

// 1 기본빵 때문에 헷갈려서 온갖 인덱스 오류 저지름

vector<vector<int>> mentor_cases;

void RCombi_Mentor(int remain, int type, vector<int>& mentor_case)
{
    if (type+1 == mentor_case.size()){
        mentor_case[type] = 1+remain;
        mentor_cases.push_back(mentor_case);
        return;
    }

    for (int i = 0; i <= remain; ++i) {
        mentor_case[type] = 1+i;
        RCombi_Mentor(remain - i, type+1, mentor_case);
    }
}

int TotalWait(vector<int>& mentor_case, vector<vector<int>>& reqs)
{
    // mentor_case에 맞게 mentorq의 각 원소에 있는 pq 사이즈 설정
    vector<priority_queue<int, vector<int>, greater<int>>> mentorq(mentor_case.size());
    for (int type = 1; type < mentor_case.size(); ++type) {
        int count = mentor_case[type];
        while (count--) { mentorq[type].push(0); }
    }

    int total_wait = 0;
    for (vector<int> req : reqs) {
        int start = req[0];
        int duration = req[1];
        int type = req[2];

        int mentor_end = mentorq[type].top();
        mentorq[type].pop();
        // 상담 요청을 받으면서 멘토 상태 확인
        // 멘토 free 시점이 start 이전이면 이번 요청 종료는 요청 시작 + 상담 시간
        if (mentor_end < start) { mentorq[type].push(start + duration); }
        // 멘토 free 시점이 start 이후이거나 같다면 대기 시간 추가
        else { 
            total_wait += (mentor_end - start);
            mentorq[type].push(mentor_end + duration);
        }
    }
    return total_wait;
}

int solution(int k, int n, vector<vector<int>> reqs) {
    // 멘토를 배치할 수 있는 모든 경우의 수를 구한다
    // 유형이 20개 까지면 중복 조합이니 계산 가능
    // 각 유형은 우선순위 큐로, 멘토는 그 안에 든 원소에 대응됨
    // 모든 멘토 경우의 수를 시뮬해보고, 가장 낮은 대기 시간을 반환
    
    // k : 상담 유형, n : 멘토 명수
    vector<int> mentor_case(k+1); // mentor_case는 각 경우의 수 담을 임시 객체
    RCombi_Mentor(n-k,1,mentor_case); // mento_cases에 경우의 수 할당

    int min_wait_time = 100 * 3000000;
    for (vector<int> mentor_case : mentor_cases) {
        min_wait_time = min(TotalWait(mentor_case,reqs),min_wait_time);
    }

    return min_wait_time;
}

int main()
{
    vector<vector<int>> reqs1 = { {5, 55, 2} ,{10, 90, 2},{20, 40, 2},{50, 45, 2},{100, 50, 2} };
    cout << solution(2, 3, reqs1);
}