[99클럽] 코테 스터디 19일차 TIL - DP(1043. Partition Array for Maximum Sum)

문제

문제 설명

• 입력
  정수 배열 arr가 주어집니다.
  정수 k가 주어집니다. (1 <= k <= arr.length)
• 목표
  배열 arr를 몇 개의 부분 배열로 분할하여 각 부분 배열의 크기가 최대 k가 되도록 합니다.
  각 부분 배열의 합을 최대화하는 것이 목표입니다.

제한 사항

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 109
• 1 <= k <= arr.length
• 예시
• Example 1
  Input: arr = [1,15,7,9,2,5,10], k = 3
  Output: 84
  Explanation: arr becomes [15,15,15,9,10,10,10]
• Example 2
  Input: arr = [1,4,1,5,7,3,6,1,9,9,3], k = 4
  Output: 83
• Example 3
  Input: arr = [1], k = 1
  Output: 1

풀이 방법

풀이 핵심

1. arr[o]~arr[i]까지는 최대 합을 계산하는 dp[i] 배열을 arr[] 길이만큼 초기화한다.
2. i=0~arr[] 길이를 순회하며 dp[i]에서 최대 합을 계산한다.
   1. 각 i에 대해 부분 배열의 길이가 1~k인 부분 배열을 계산한다.
   2. 1에서 구한 부분 배열의 값 중 최대 값을 dp[i]에 저장한다.
3. 최대 값인 dp[arr.length-1]값을 return한다.

부분 배열의 길이가 1~k인 경우를 모두 구한 후 최대 값을 dp[i]에 저장

• i=2일 때 부분 배열의 길이가 1, 2, 3일 때를 모두 구한 후 최대 값을 dp[2]에 저장

• i=3일 때 부분 배열의 길이가 1, 2, 3일 때를 모두 구한 후 최대 값을 dp[3]에 저장

• i=4일 때 부분 배열의 길이가 1, 2, 3일 때를 모두 구한 후 최대 값을 dp[4]에 저장

코드

/**
dp[] 배열에 0~n까지 최대값을 순차적으로 계산
마지막 dp[n] == 최대값 */

import java.util.*;
class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int[] dp = new int[arr.length];
        for(int i = 0 ; i < arr.length; i ++){
            int max = 0;
            // j = 부분 배열의 길이
            for(int j= 1; j < k + 1; j ++){
                // idx = 부분 배열의 시작 인덱스
               int idx = i - j + 1;
               if (idx < 0){
                   continue;
               }
               // max = 현재 부분 배열의 최대 값
               max = Math.max(max, arr[idx]);
               // 배열의 첫 값부터 j까지 max로 채운다.
               if (idx == 0){
                   dp[i] = Math.max(dp[i], max * j);
                   continue;
               }
               // dp[idx-1] = idx-1 까지의 최대 값
               dp[i] = Math.max(dp[i], dp[idx - 1] + max * j);
            }
        }
        return dp[arr.length - 1];
    }
}

오늘 회고

눈으로만 볼 땐 이해가 안 갔는데 그려보니 바로 이해가 간다.
막상 이해하면 쉬운데 처음 볼 땐 왜이리 어려운지 모르겠다.

다음부턴 바로바로 쓰고 그리면서 이해해보자...
오늘도 고생했다 !!