[LeetCode] DP : Minimum Difficulty of a Job Schedule (Java)

들어가며

문제 자체에 대한 설명과 예제 테스트케이스가 짧아 여러 경우를 다 고려하는 것을 알아서 생각해야 했습니다. 
그러니까 Hard 단계 문제이겠지만... 
저 또한 스스로 풀고 틀린 이후 문제를 이해하기 위해 이런 저런 그림을 그려보았는데, 도움이 될까 싶어 정리해보았습니다.

 
 

👉  문제 바로가기 👈

 

---

문제 파악

1. n개의 작업을 d일 동안 진행하고, 하루에 최소 하나의 일을 해야 한다.
2. j의 작업을 하기 위해서는 j-1 작업을 완료해야 한다.
3. 6 4 2 4 의 jobDifficulty를 가진 작업을 하루에 한다면 그 날의 일당은 구간에서 최댓값인 6이 된다.
4. d일 동안 최소한의 총 소요 일당을 구한다.
5. 작업을 완료할 수 없거나 조건에 부합하지 않으면 -1을 반환한다.
 
 

접근 방법

예를 들어 [1,3,2,5,7,2,4,8] 을 d = 4 일동안 나눠서 처리하는 예시를 생각해보겠습니다.
문제에서 순서대로 일을 진행해야 하는데, 매일 최소 1개 이상의 작업을 처리해야 한다고 합니다.
그러면 우리는 고등학교 때 배운 내용이 떠오를 수 있습니다.
전체 일자에 하루에 1개씩을 일단 배분하고 나머지 값을 배분하면 전체 나누는 경우가 됩니다.
즉 8개의 일을 4일 동안 나누면
1 1 1 1 을 각 하루에 분배하고 나머지 4개의 일을 분배하는거죠
 

2개씩 나누는 경우

• 4 0
• 3 1
• 2 2
• 1 3
• 0 4

3개씩 나누는 경우

• 1 1 2
• 1 2 1
• 2 1 1

4개씩 나누는 경우

• 1 1 1 1

즉, 전체 배열에서 칸막이를 어디에 두어야 하는지 골라야 합니다.

저는 사실 여기까지만 생각하고, 아 근데 이러면 이거를 다 구해야 하나? 시간초과나는데... 하고 구현하지 못했습니다
 
이런식으로 칸을 나누면

• 1일째에 1
• 2일째에 3
• 3일째에 2
• 4일째에는 최대값인 8을 jobDifficulty로 가지게 됩니다

 
칸막이를 위 그림처럼 여러 방식으로 놓을 수 있습니다.
1일차에 1개의 일만 한다고 생각하고, 2일차부터 보면 2일차에 하는 일을 위와 같이 볼 수 있습니다.
그러면 현재 날짜, 작업 수 → 2개의 변수가 바뀌고 있습니다 → dp는 2차원 배열입니다.
i는 일, j는 작업을 의미합니다.
 
 

그럼 이제 dp가 정확히 무엇을 메모이제이션하는지 보겠습니다

 
2일차에 여러가지 일을 한다면 그 중 가장 jobDifficulty가 높은 일이 해당 요일에 소요된 difficulty일 것입니다.
우리는 최종적으로 총 d일동안 소요된 최소 difficulty의 합을 구해야 하므로
dp[i][j]에는 i일에 j번째 까지 일을 했을 때 소요되는 최소 합 으로 하겠습니다
 

빨간색으로 dp의 내용이 추가

 
 

초기화하기

 
초기화를 할 때는 매일 최소 1개씩은 작업을 해야 하므로
1 ~ ≤ n - d + 1까지 초기화가 가능합니다.
1일차에는 범위 내 작업 중 최대값을 찾으면 됩니다.

• 1
• 1 , 3
• 1, 3, 2
• 1, 3, 2, 5
• 1, 3, 2, 5, 7

이므로 범위를 처음부터 끝까지 하지 않고, dp[i][j-1]에는 직전까지의 최댓값이므로 직전 값과 최대값을 비교 갱신합니다.
 
 

위 그림에서 max(1~1번 작업) 이어야 합니다. job은 0번 인덱스부터 하니까요. 그림에 잘못 표시되었습니다.

 
2일차에는 1일차까지 했던 작업 + 현재 범위에서 최대값을 더해주면 됩니다.
 
 
dp[i][j]는 i번째 일에 j번 작업을 할 때의 최소 누적 합입니다. 즉,

 
3번째 일, 즉 여기서 동그라미한 2번 일을 할 때
그 전날 인 1일차에 할 수 있는 경우가 나뉠 수 있습니다.
이것을 dp에 적용하면 다음과 같습니다.
 

 
이때 추가 최적화를 하는 과정에서 역순으로 dp값을 갱신하면 연산을 줄일 수 있습니다.

 
이 그림처럼 dp[2][4] 일때 전날에 한 작업 일당에서 현재 구간의 최댓값을 구한 최소 값을 구해야 합니다.
그런데 정방향으로 하면 범위를 처음부터 ~ 끝까지 계속 반복하며 max 값을 구해야 합니다.
하지만 역방향으로 하면 max 값만 갱신하면서 O(1) 시간복잡도로 최댓값을 구할 수 있습니다.
 

코드 구현

import java.util.*;

class Solution {

  static final int INF = Integer.MAX_VALUE;
  
    public int minDifficulty(int[] jobDifficulty, int d) {
      int n = jobDifficulty.length;
      if ( n < d ) return -1;
      int[][] dp = new int[d+1][n+1];

      // 1. 초기화
      dp[1][1] = jobDifficulty[0];
      for(int i = 2; i <= n - d + 1; i++){
        dp[1][i] = Math.max(dp[1][i-1], jobDifficulty[i-1]);
      }

      // 2. 2일차부터 d일차까지
      for (int r = 2; r <= d; r++) {
        for (int c = r; c <= n-d+r; c++) {
            int maxDiff = 0;
            dp[r][c] = Integer.MAX_VALUE;
            
            // 역방향으로 탐색하며 최댓값 갱신
            for (int k = c; k >= r; k--) {
              maxDiff = Math.max(maxDiff, jobDifficulty[k-1]);
              dp[r][c] = Math.min(dp[r][c], dp[r-1][k-1] + maxDiff);
            }
        }
      }
      return dp[d][n];
    }
}