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

오늘의 과제

리트코드 Medeum으로 분류된 Partition Array for Maximum Sum입니다.

 

문제의 유형은 어제에 이어 DP(Dynamic Programing)입니다.

문제

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

 

 

먼저 문제 요구사항 요약입니다.

 

정수 배열 arr과 정수 k가 주어질 때 arr을 최대 k 길이의 하위 배열로 분할 후

각 하위 배열에서 가장 큰 숫자만 남긴 후 더한 값 중 최대값을 반환하면 됩니다.

 

먼저 초기식을 구해봅니다.

 

dp[i]가 있을 때 안에 들어갈 값은 처음 값부터 i까지의 숫자를 돌렸을 때의 최대합을 저장합니다.

 

즉, dp[0]일 때에는 숫자가 하나만 있으니 해당 숫자 자체가 최대합임으로

dp[0]은 arr[0]이 됩니다.

 

이제 문제의 예시 배열로 dp를 구해봅니다.

arr = [1, 15, 7, 9, 2, 5, 10], k = 3

 

dp[0] = 1

dp[1] = 30

dp[2] = 45

 

dp[0]은 위에 언급했듯 길이가 1이니 0번째 인덱스가 들어갑니다.

 

dp[1]은 1, 15를 사용할 수 있으니 길이가 1인 하위 배열과 길이가 2인 하위 배열을 고려할 수 있습니다.

문제의 조건에 따라 하위 배열로 엮이면 해당 배열 내 최대값으로 변하니 아래와 같이 계산되어집니다.

 

길이가 1일때 => 15

길이가 2일때 => [1, 15] => [15, 15] => 30

 

dp[2]는 1, 15, 7을 사용하며 길이가 3인 배열까지 잘라볼 수 있습니다.

15가 껴있으니 [1, 15, 7] => [15, 15, 15] => 45 입니다.

 

위 수식을 계속 반복하면 됩니다.

 

 

 

코드입니다.

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

        // 첫 번째 요소는 자기 자신이 최대 합
        dp[0] = arr[0];
        
        // 모든 요소에 대해 dp 계산
        for (int i = 0; i < n; i++) {
            int maxInPartition = 0;
            // j는 현재 위치부터 k 이내의 길이를 나타냄
            for (int j = 1; j <= k && i - j + 1 >= 0; j++) {
                // 현재 partition 내의 최대 값 갱신
                maxInPartition = Math.max(maxInPartition, arr[i - j + 1]);
                // dp 값 갱신
                // i - j는 음수이면 안된다.
                dp[i] = Math.max(dp[i], (i >= j ? dp[i - j] : 0) + maxInPartition * j);
            }
        }

        return dp[n - 1];
    }
}

 

배운 점

DP가 시작되자마자 벽에 부딪혀 한계를 느끼고 있습니다.

 

설명을 적을 때에는 점화식만 찾으면 간단히 풀린다고 하고 있는데 그 점화식을 찾기가 너무 어렵네요.

 

오늘의 문제 또한 직접 풀지 못했고 다른 사람의 풀이를 참고하여 이해하며 작성했습니다.

 

좌절하고 싶지만 어떻게든 강제로라도 머리에 우겨넣다 보면

스스로 이해하고 풀어나갈 수 있는 실력이 생긴다고 믿습니다.

 

코테는 꾸준함입니다.

 

어떻게든 꾸준히 풀어내겠습니다.

 

 

오늘의 한줄평

벽에 부딪혔다는 것은 한 단계 더 성장할 수 있는 기회라는 뜻이다.