[LeetCode] 1335. Minimum Difficulty of a Job Schedule

https://leetcode.com/problems/minimum-difficulty-of-a-job-schedule/description/

Minimum Difficulty of a Job Schedule - LeetCode

leetcode - Minimun Difficulty of a Job Schedule

문제 유형 : 다이나믹 프로그래밍 / 재귀

문제 난이도 : Hard

 

 

문제

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the ith job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done on that day.

You are given an integer array jobDifficulty and an integer d. The difficulty of the ith job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

 

당신은 d일동안 일을 정해진 리스트순으로 해결해야 한다. (앞에 있는 일들은 다 해놔야 한다)

당신은 매일 하나의 일을 최소한 해야 한다.

일 스케줄의 난이도는 d일동안의 각각 하루의 최고난이도를 합친 값이다.

당신은 정수 배열 jobDifficulty와 정수 d를 받는다. i번째 업무의 난이도는 jobDifficulty[i]이다.

일 스케줄의 최소 난이도를 반환하라. 스케줄을 조정할 수 없다면, -1을 반환하라.

 

 

풀이

처음에 그리디로 풀려고 하였으나, 제출하고 실패하는 걸 보고 바로 dp를 생각했다.

dp[task][d] = 최소 스케줄난이도로 설정한다.

 

탑-다운 방식의 dp에서는 dp[시작인덱스][남은날짜수]로 정하고,

바텀업 방식의 dp에서는 dp[진행한인덱스][진행한날짜수]로 정한다.

 

탑다운 방식의 풀이)

1. 기저 상황: 시작인덱스가 n보다 크면, 1e9반환
2. 기저 상황: 남은 날짜가 0인 경우
   • 시작인덱스가 n이면(모든 업무 완료): 0 반환
   • 아니라면(모든 업무 완료하지 못하면): 1e9반환
3. 기저상황: 남은 날짜가 0이 아닌데 시작인덱스가 0이면(모든 업무 완료): 1e9 반환
4. dp테이블에 값이 있으면(-1이 아니면), 테이블 값 반환
5. 최소값을 구하기 위한 반복문 실행: 하위 케이스 
   1. 최대 난이도 날짜 업데이트
   2. 최소값 갱신: 현재의 최고 난이도날짜 + 나머지 부분배열의 최소 스케줄난이도 구하기
6. dp테이블에 저장하고, 반환

메인 메소드에서, dp테이블을 처음에 전체 -1로 초기화시키고, 만약 d가 n보다 크면, -1반환.(애초에 안 되는 경우)

재귀 함수 호출한 값을 반환하여 값 제출

 

바텀업 방식의 풀이)

1. dp테이블을 탑다운과는 반대로 1e9로 초기화시킨다.
2. 이중for문을 순회한다. (i : 1 ~ n * j : 1 ~ d)
3. i번째보다 1 작은값부터 j-1까지의 진행했던 이전 일들을 확인하면서, j날짜의 최대업무난이도를 업데이트하며 최소 스케줄난이도값 갱신(j-1인 이유는 유효한 범위 때문에(적어도 하루에 하나의 일을 해야 하므로, 지난 업무들을 i번째 날에 하는 경우로 끌어올 때, 최소 개수를 맞춰야 함))
   • 점화식은 dp[i][j] = min(dp[i][j], maxNum + dp[k][j-1])이 됨.
4. dp[n][d] 반환. 만약 1e9인 경우, 스케줄링이 불가능하므로 -1 반환.

 

 

코드

C++

 

탑다운 재귀

class Solution {
public:
    int dp[301][11];
    vector<int> jobDiff;
    int n;
    int solve(int idx, int leftday) {
        if(idx > n) return 1e9;
        if(leftday == 0) {
            if(idx == n) return 0;
            else return 1e9;
        }
        else if(idx == n) return 1e9;
        
        if(dp[idx][leftday] != -1) return dp[idx][leftday];

        int maxInt = jobDiff[idx];
        int result = 1e9;

        for(int i = idx; i < n; i++) {
            maxInt = max(maxInt, jobDiff[i]);
            result = min(result, maxInt + solve(i+1, leftday-1));
        }

        return dp[idx][leftday] = result;
    }

    int minDifficulty(vector<int>& jobDifficulty, int d) {
        jobDiff = jobDifficulty;
        memset(dp, -1, sizeof(dp));
        n = jobDiff.size();
        if(n < d) return -1;

        return solve(0, d);
    }
};

 

바텀업 3중for문

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) {
        const int n = jobDifficulty.size();
        if (n < d) return -1;

        vector<vector<int>> dp(301, vector<int>(11, 1e9));
        dp[0][0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= d; j++) {
                int maxNum = -1;
                for (int k = i - 1; j - 1 <= k; --k) {
                    maxNum = max(maxNum, jobDifficulty[k]);
                    dp[i][j] = min(dp[i][j], maxNum + dp[k][j - 1]);
                }
            }
        }

        return dp[n][d] == 1e9 ? -1 : dp[n][d];
    }
};