1723 Find Minimum Time to Finish All Jobs

https://leetcode.com/contest/weekly-contest-223/problems/find-minimum-time-to-finish-all-jobs/

처음에 비트맵에 DP로 풀었다가 C++은 아슬아슬하긴 해도 통과하지만, 파이썬은 바로 시간 초과 나길래

그냥 Discussion에서 훌륭한 풀이를 가져왔다.

 

https://leetcode.com/problems/find-minimum-time-to-finish-all-jobs/discuss/1042898/Most-performant-C%2B%2B-so-far-beats-100-runtime-99-memory

 

 

C++

class Solution {
public:
    int minimumTimeRequired(vector<int>& inputJobs, int k) {
        jobs = move(inputJobs);
        totalWorkers = k;
        workLoad.resize(jobs.size());
        search(-1, 0);
        return minLoad;
    }
    
private:
    vector<int> workLoad, jobs;
    int minLoad = INT_MAX, currentMax = 0, totalWorkers = 0;
    void search(int rightMostSlot, int current) {
        if (current >= jobs.size()) {
            minLoad = min(minLoad, currentMax);
            return;
        }
        for (int i =  min(rightMostSlot + 1, totalWorkers - 1) ; i >= 0; -- i) {
            int oldMax = currentMax;
            workLoad[i] += jobs[current];
            currentMax = max(workLoad[i], currentMax);
            if (currentMax < minLoad) 
                search(max(i, rightMostSlot), current + 1  );
            workLoad[i] -= jobs[current];
            currentMax = oldMax;
        }
    }
};