99클럽 코테 스터디 20일차 TIL Partition Array for Maximum Sum

https://leetcode.com/problems/partition-array-for-maximum-sum/submissions/1281377816/

 

 

 

 

1. 문제 및 접근

 

1043. Partition Array for Maximum Sum

 

arr가 주어지면 최대 k개의 subarr로 만드는데,

합이 가장크게 만들어라 그 서브 어레이는 젤 큰 값으로 변경시키자

1. 어떻게 나누느냐가 중요한데, 어떻게 dp에 이 정보들을 저장하지..

 

일단 k개로 짤랐을 때 7개의 배열을 k인 3으로 짜르면 3개의 배열이 나오는데

작은 수가 있다면 제일 큰수에 포함시켜 바꿔주고, 그다음 제일 큰 수가 포함된 배열로

{15,15,15} {10,10,10} {9}의 형태로 작은 수들은 큰 수로 다 바꿔주는 형태가 베스트일듯

dp로 어떻게 접근하고,, 갱신해가면서 저장해줄까 아휴 ㅠ

 

 

2. 풀이

 

public static void main(String[] args) {
    partitionArrayforMaximumSum main = new partitionArrayforMaximumSum();
    int[] arr = new int[]{1, 15, 7, 9, 2, 5, 10};
    int k = 3;

    int answer = main.maxSumAfterPartitioning(arr, k);
    System.out.println(answer);
}

public int maxSumAfterPartitioning(int[] arr, int k) {
    int n = arr.length;

    dp = new int[n + 1];


    for (int i = 1; i <= n; i++) {
        int max = 0;
        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[n];
    

}

 

전체 풀이

 

 

 

 

 

2-1. DP접근

 

 

n을 arr의 크기로 정해준 후

 

dp의 index 접근 및 i-j 위해 n+1 해주는 게 항상 직관적이라 편하다.

 

(예전엔 0을 시작 Index로 관리하는 게 더 멋있어 보였어..)

 

 

 

 

 

2-2. dp 배열 채우기 (외부 For)

 

 

dp배열은  1, 2, ... 채워 나가는 것이 저장된 최대 값이다.

 

dp[i] 값은 n개까지 돌면서 들어온 dp[n]의 값엔 그 배열의 최대 sum값이 저장되어 있을테니, i~n까지

 

 

 

 

 

2-3. 내부 For

 

 

 

내부에선 현재 올 수 있는 최대 값들을 돌면서 계속 생신해준다.

 

j는 고려 해야할 것이 j가 최대 K까지 돌껀데 (부분 배열은 최대 k개 까지 가질 수 있으니까)

하나 더 생각 해야할 것이 arr의 index를 벗어나지 않게 (음수가 오지 못하게)

 

그리고 j를 돌면서 저장된 (k개의 부분 배열 중 이때까지의 가장 큰 값과 현재 arr[i-j] 중 값을 비교해서 max로 저장!

 

최종적으로 dp[i]에 저장될 값은 j를 계속 돌면서 부분 배열 중에 저장된

 

dp[i]의 값(이미 저장된) vs k개의 배열 중 큰 값으로

 

이해도 어려운데, 설명도 어렵다 ㅠㅠ 나도

 

 

 

하나의 예시로 [1, 15, 7] 의 배열을 보자면, dp[3]에 저장될 값은 계속 갱신되는데, 사실 dp[2]에 30이 저장되어 있으니

 

 

 

 

30 + 현재 arr[index] 7 인 37 vs 30 + max 값 15가 더해져 45

 

 

 

 

즉 [15,15,7] vs [15,15,15] 중 큰 수가 저장된다고 생각하면 됨!

 

 

 

 

 

 

 

2-4. 마무리

 

 

 

 

 

사실 내가 푼 게 아니고, GPT형님이 다 풀어줬다..

 

진짜 dp를 꾸준히 했는데 항상 어려운 거 같다 ㅠㅠ

제일 문제가 top-down의 감을 익히면 bottom-up이 안되고, 점화식도 안 떠오르고 진짜..

 

제일 무력해지는 것 같다..