[DFS+우선순위큐] 프로그래머스 상담원 인원 C++

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

 

자연수의 분할 P(n,k) <= P(20,5) = P(15,1)+...+P(15,5) = 1+7+19+27+30 <= 100

 

DFS O(300*100*5!) = O(3,600,000)

우선순위큐 O(300log300) < O(3,000)

#include <string>
#include <vector>
#include <queue>

using namespace std;

int K, N, answer;
vector<vector<int>> Reqs;

void simulation(vector<int> v) {
    priority_queue<int, vector<int>, greater<int>> pq[K]; // 오름차순
    for(int i=0; i<K; i++) {
        for(int j=0; j<v[i]; j++) pq[i].push(0);
    }
    
    int delay = 0;
    for(auto req : Reqs) {
        int type = req[2] - 1; // 상담 유형
        
        int num = pq[type].top();
        pq[type].pop();

        if (req[0] >= num) pq[type].push(req[0] + req[1]); // 요청 시간 <= 멘토 상담 끝 시간 : 대기X
        if (req[0] < num) { // 요청 시간 < 멘토 상담 끝 시간: 대기O, 먼저 상담 요청한 참가자 우선
            delay += (num - req[0]);
            pq[type].push(num + req[1]);
        }
    }
    
    answer = min(delay, answer);
}

void partition(vector<int> v, int idx, int left) { // K개의 합이 N인 자연수의 분할(순열)
    if ((idx > K) || (left < 0)) return;
    if ((idx == K) && (left == 0)) {
        simulation(v);
        return;
    }

    for(int i=1; i<=left; i++) {
        v[idx] = i;
        partition(v, idx+1, left-i);
    }
}

int solution(int k, int n, vector<vector<int>> reqs) {
    answer = 1e9;
    K = k; N = n;
    Reqs = reqs;
    
    partition(vector<int>(n+1,0), 0, n);
    
    return answer;
}