LeetCode 1335

문제 링크

문제 설명.

생각이 필요한 DP문제.
순서대로 해야하는 일들이 있어서 그 난이도 jobDifficulty : list와 일을 하는 날의 수 k : int가 주어진다. 각 날에 일은 최소 한번 이상 해야한다.
각 날에 한 일의 난이도는 그날 한 일의 최대 난이도와 같다.
모든 날의 난이도의 최솟값을 구하라.

example.

jobDifficulty = [6,5,4,3,2,1], d = 2

첫날 한 일이 1개인 경우, 최솟값은 6+max([5,4,3,2,1]) == 11이 된다.
그리고 이 예시의 최솟값은 첫날 5개의 일을 처리하고, 둘쨋날 마지막 일을 처리하는 것이 최솟값이 나온다.
max([6,5,4,3,2])+1 == 7

풀이.

어떻게 DP를 짜면 좋을지 좀 오래 생각했었다. 결과적으로 이중배열을 통해 BF가 혼합된 양식으로, 그리고 lru_cache를 사용해서 문제를 풀었다.

그리고 dp : list의 index i,j에 따른 값은 다음과 같다.

• dp[i][j] : j번째 날 i번째 일까지 했을 때의 최솟값.

이 때 고려해야할 3가지 점은

1. dp[-1]의 값들은 반드시 jobDifficulty의 마지막까지 고려를 해야한다는 점.
2. i<j인 경우 하루에 최소 한번의 일을 해야하기 때문에 고려하지 않는다는 사실(따라서 초깃값을 d*len(jobDifficulty)를 최댓값으로 세팅해주고, 계산에서 제외시킨다.).
3. len(jobDifficulty)와 d의 관계, 그리고 d == 1일 때 코드의 예외케이스.

으로 이리저리 채점결과를 틀리게 했던 다양한 케이스가 존재했다.

풀이 코드.

class Solution:
    def minDifficulty(self, jobDifficulty: List[int], d: int) -> int:
        leng = len(jobDifficulty)
        if leng < d:
            return -1
        elif leng == d:
            return sum(jobDifficulty)
        elif d == 1:
            return max(jobDifficulty)
        
        dp = [[3000000 for _ in range(leng)] for i in range(d)]
        
        @lru_cache(maxsize = None)
        def maxi(i,j=leng-1):
            return max(jobDifficulty[i:j+1]) if i<j else jobDifficulty[i]
        
        num = jobDifficulty[0]
        for i in range(leng):
            if num<jobDifficulty[i]:
                num = jobDifficulty[i]
            dp[0][i] = num
        # define first days.
        # In dp[0], each value of dp[0][i] = max(jobDifficulty[:i])
        
        for i in range(1,d-1):
            for j in range(i,leng):
                for k in range(i-1,j):
                    tmp = dp[i-1][k]+maxi(k+1,j)
                    if dp[i][j] > tmp:
                        dp[i][j] = tmp
        
        for j in range(d-1,leng):
            for k in range(d-2,j):
                tmp = dp[-2][k]+maxi(k+1)
                if dp[-1][j] > tmp:
                    dp[-1][j] = tmp
        
        # for i in dp:
        #     print(i)
        maxi.cache_clear()
        
        return min(dp[-1][d:])

잡담.

1. 이번 문제는 LeetCode에서 드물게 어려웠던 문제였다. 지난주 일요일의 Daily 문제였는데 생각할 것이 많은 문제였어서 고민하다가 올리게 되었다.
2. 워낙 2D1P용 포스팅으로 어제 올리려 했으나 면접보랴, 프로젝트 진행하랴, 은행업무보랴 정신이 없어서 깜박하고 스킵했다...ㅠㅠ