99클럽 코테 스터디 15일차 TIL - DP

오늘의 학습 키워드

DP

---

알고리즘 문제

• LeetCode Medium 1043. Partition Array for Maximum Sum
• https://leetcode.com/problems/partition-array-for-maximum-sum/description/

---

공부한 내용

DP

• 일반적으로 배열을 사용해서 해결한다.
• 배열의 쓰임은 하위 문제들의 결과를 저장해 두었다가 나중에 필요할 때 재사용하기 위함이다.
• 보통 배열은 상태를 저장해둔다.

---

오늘의 회고

처음 시도

• 최댓값을 구해서 최댓값을 기준으로 그 최대값을 포함해 앞뒤로 k만큼까지 개수를 늘려가면서 파티셔닝을 해보려고 했다.
• 최댓값이 여러개가 있을 경우 등 여러가지 경우의 수가 생겨 기준을 잡기 어려웠다.

해결

• 주어진 배열 arr [1, 15, 7, 9, 2, 5, 10], k=3
• 주어진 배열에서 변수(i)로 인덱스 1부터 벽을 만든다.
• 벽-1 위치에서부터 부분 배열을 만든다. (파티셔닝)
  • 인덱스 0 ~ 부분 배열 시작 인덱스 -1 => 부분 배열이 아닌 부분
  • 부분 배열 시작 인덱스 ~ 벽 -1 => 부분 배열 (최대 k개)
• 부분 배열은 벽-1 위치에서부터 j개로 시작한다. (j=1) / 부분 배열의 최댓값 max는 0으로 초기화한다. 
• 부분 배열은 1개씩 개수를 늘려 k개까지 늘려가면서 부분 배열의 최댓값을 구해서 dp 배열에 저장한다.
  • 처음 부분 배열은 벽 바로 앞에 값 1개일 것이다. 예를 들어 i=3이면, j=1부터 시작하니까 arr[2] = 7이 부분배열, 이 때 부분배열의 최댓값은 값이 1개이므로 "7"이 최댓값이 된다(max=7)
  • 부분 배열 개수를 +1해서 j=2이면, arr[1]=15과 arr[2]=7로 [15, 7]이 부분배열이 된다. 이 때, 부분배열의 최댓값은 max와 새로 추가된 15와 비교해 더 큰 값이므로 15가 최댓값이 된다.(max=15)
  • 부분 배열 개수를 +1해서 j=3이면, k=3이니까 마지막 부분 배열을 만들게 된다. arr[0]=1, arr[1]=15, arr[2]=7로 [1, 15, 7]이 부분배열이 된다. 이 때, 부분배열의 최댓값은 max와 새로 추가된 1을 비교해 큰 값이므로 그대로 둔다.
• 여기까지 부분배열과 부분배열의 최댓값을 구하는 로직이었고, 부분배열만이 아닌 전체 최대합을 구하기 위해 dp 배열을 이용해야 한다. 
  • 전체 최대 합은 부분배열의 최대 합 + 부분 배열이 아닌 값들의 최대 합이다.
  • 그런데 dp 배열에 0번 인덱스부터 시작해 최대합을 저장하게 되면 이전에 구했던 최대합들을 이용해 현재 최대합을 계산하기 쉽게 된다.
  • 마치 이런거다. 벽으로부터 1개, 2개, .., k개까지 각각 부분배열을 만들어서 비교해야 하는데 부분배열이 아닌 값들의 최대합을 또 계산해야 전체 최대합을 구할 수 있다. 그치만 dp[0], dp[1] 이런 식으로 각 상황마다 최대합을 저장해두면, 그 상황에 갔을 때 합을 꺼내오면 되기때문에 재사용할 수 있다는 것이다. 
    => 내가 생각한 dp 배열은 추후에 같은 상황이 올 때 값을 꺼내기 위해 상황마다 값을 저장해둔다고 생각이 든다.
  • 내가 이해하기 쉽게 풀면,
    • dp[0] 은 주어진 배열 arr의 0번 인덱스 이전의 값들의 최대 합 => 0번 인덱스 이전 값은 없으므로 0
    • dp[1] 은 arr의 1번 인덱스 이전의 값들의 최대 합 => dp[1] = 벽이 1일때 부분배열 최대합 => arr[0] = 1
    • dp[2] 는 arr의 2번 인덱스 이전의 값들의 최대 합 => dp[2] = 벽이 2일 때 부분배열 최대합
      => dp[2] = dp[1] + [15] = 1 + 15 =16 / dp[2] = dp[0] + [1, 15]의 최대합 = 0 + 15*2 = 30 
      => 16 vs 30 최대합 => dp[2] = 30
    • dp[3] 은 arr의 3번 인덱스 이전의 값들의 최대 합 => dp[3] = 벽이 3일 때 부분배열 최대합
      => dp[3] = dp[2] + [7] = 30 + 7 = 37 / dp[3] = dp[1] + [15, 7]의 최대합 = 1 + 15*2 = 31 / 
           dp[3] = dp[0] + [1, 15, 7] = 0 + 15*3 = 45 
      => 37 vs 31 vs 45 최대합 => dp[3] = 45
    • dp[4] 는 arr의 4번 인덱스 이전의 값들의 최대 합 => dp[4] = 벽이 4일 때 부분배열의 최대합
      => dp[4] = dp[3] + [9] = 45 + 9 = 54 / dp[4] = dp[2] + [7, 9] = 30 + 9*2 = 48 /
           dp[4] = dp[1] + [15, 7, 9] = 1 + 15*3 = 46 
      => 54 vs 48 vs 46 => dp[4] = 54
    • ... 이렇게 dp[벽] 현재 벽을 세웠을 때 벽이 있는 곳 전까지의 최대합이 dp 배열에 저장된다!!!!
• 그렇게 주어진 배열을 모두 돌아서 dp에 채우면 dp 배열의 마지막 인덱스가 arr 전체 최대합이 된다.

---

문제 풀이

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
       int len = arr.length;
       int dp[] = new int[len+1];   //배열 한칸씩 옮기면서 최댓값 계산하고 저장할 배열

       for (int i = 1; i <= len; i++) {
            int max = -1;   //부분 배열의 최댓값
            for (int j = 1; j <= k && i-j >= 0; j++) {
                max = Math.max(max, arr[i-j]);
                dp[i] = Math.max(dp[i], dp[i-j]+(max*j));
            }
       }

       return dp[len];
    }
}