[LeetCode] 1335번. Minimum Difficulty of a Job Schedule (Python 파이썬)

문제

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.

 

Example 1:

Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 

Example 2:

Input: jobDifficulty = [9,9,9], d = 4
Output: -1
Explanation: If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.

Example 3:

Input: jobDifficulty = [1,1,1], d = 3
Output: 3
Explanation: The schedule is one job per day. total difficulty will be 3.

 

Constraints:

• 1 <= jobDifficulty.length <= 300
• 0 <= jobDifficulty[i] <= 1000
• 1 <= d <= 10

풀이

난이도가 hard 인데 꽤 쉬웠다. 근데 자잘한 실수때문에 결국 시간은 꽤 걸렸다. 

 

원리

 

2차원 dp 로 풀어야 한다. 

[6,5,4,3,2,1] 에서 4개까지 [6,5,4,3] 의 3일의 스케줄의 최소 난이도를 구한다고 하면, 

 

세번째 스케줄을 고르는 경우는 두번째 스케줄까지 고른 경우에서 한 스케줄을 더한 경우이다. 

 

세번째 스케줄을

 

2번째부터 고르는 경우: 2일의 스케줄의 1개까지의 최소난이도 + 2번째부터 4개까지의 스케줄 중 최대값

3번째부터 고르는 경우: 2일의 스케줄의 2개까지의 최소난이도 + 3번째부터 4개까지의 스케줄 중 최대값

4번째부터 고르는 경우: 2일의 스케줄의 3개까지의 최소난이도 + 4번째부터 4개까지의 스케줄 중 최대값 ([6,5,4] 최소난이도 + [3] 부터 고른 최소 난이도)

 

이게 가능한 이유는 고른 날짜를 기준으로 왼쪽, 오른쪽 배열 두개로 나누면, 왼쪽 배열은 불확실한 값, 오른쪽 값은 확실한 값

(고른 수 부터 오른쪽배열에 모두 스케줄에 담아야 하므로 고른 수 들 중 max 값이 오른쪽 배열의 최소난이도가 된다.) 

 

이것을 식으로 세운다.

dp[i][j] 를 j 까지의 스케줄 중 i days 로 나눴을 때, 최소 난이도라고 하면,

 

dp[i][j] = min(dp0+max1, dp1+max2 ,dp2+max3 ,dp3+max4)

 

dp0 은 1을 뺀 days 에서 0 인덱스까지 골랐을 때 최소 난이도 

 

이것을 k for 문을 돈다. 

 

6   6   6  6  6  6
INF 11  10 9  8  7
INF INF 15 13 11 9

 

여기서 위의 예시가 dp[2][3] (3days 에 4개까지의 스케줄의 최소 난이도 [6,5,4,3])

dp[2][3] 의 값은 13 인데 

 

2번째부터 고르는 경우: INF + [5,4,3] 의 최대값 

3번째부터 고르는 경우: 11 + [4,3] 의 최대값

4번째부터 고르는 경우: 10 + [3] 의 최대값

 

[6,5,4] 의 최소 난이도 10 과 3을 더해 13 으로,

3days 를 4번째 부터 고르는 경우 13 으로 최소 난이도가 된다. 

 

from typing import List

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        n = len(jobDifficulty)

        if n < d:
            return -1

        dp = [[1e9] * n for _ in range(d)]

        for i in range(n):
            dp[0][i] = max(jobDifficulty[:i+1])

        for i in range(1,d):
            for j in range(n):
                for k in range(j):
                    dp[i][j] = min(dp[i][j],dp[i-1][k]+max(jobDifficulty[k+1:j+1]))

        return dp[-1][-1]