99클럽 코테 스터디 19일차 TIL / partition-array-for-maximum-sum

partition-array-for-maximum-sum

학습 키워드: 다이나믹 프로그래밍(DP)
학습 링크: https://leetcode.com/problems/partition-array-for-maximum-sum/

문제 설명 (번역 어플 사용)

정수 배열 arr가 주어졌을 때, 배열을 길이가 최대 k인 (연속된) 부분 배열로 분할합니다. 분할 후 각 부분 배열의 값은 해당 부분 배열의 최대 값으로 변경됩니다.

분할 후 주어진 배열의 합이 최대가 되는 값을 반환하세요. 테스트 케이스는 답이 32비트 정수에 맞도록 생성됩니다.

제한 조건

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 109
• 1 <= k <= arr.length

class Solution:
    def maxSumAfterPartitioning(self, arr: list[int], k: int) -> int:
        # n: 배열의 길이
        # dp: IndexError를 피하기 위해 n+1의 길이로 초기화 해준 dynamic table
        n = len(arr)
        dp = [0] * (n + 1)
        
        # arr를 순회하면서 가장 높은 합을 dp table에 업데이트
        for i in range(1, n + 1):
        	#curr_max: dp[i]의 최댓값을 정하기 위한 용도.
            curr_max = 0
            # j: 최대 k의 길이를 검사해주기 위함. IndexError를 방지하기 위해서 min(k,i)로 막는다. 
            for j in range(1, min(k, i) + 1):
                curr_max = max(curr_max, arr[i - j])
                # dp table update, j만큼 전에 있는 원소의 값이라면 그 부분의 dp에서 떨어진만큼 curr_max를 곱해서 더해준 뒤 업데이트를 한다.
                dp[i] = max(dp[i], dp[i - j] + curr_max * j)
        
        return dp[-1]

코멘트

TIL 제출용 미들러 문제. 문제의 조건을 착각해서 오래 걸린 문제이다. 여기서 k는 배열의 개수가 아니라 부분 배열의 최대 길이이다.. of length를 못 읽고 배열의 개수로 착각해서 너무 어려운 문제로 착각했다.