[99클럽 코테 스터디 20일차 TIL] LeetCode | 1043. Partition Array for Maximum Sum

20일차 DP

Problem

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

 

Sol

주어진 배열 arr를 최대 길이 'k'인 연속된 배열로 분할하고, 각 부분 배열의 모든 값을 그 부분 배열의 최대값으로 바꾼 후 배열의 합을 최대값을 구하는 문제 (변경된 배열의 최대합 구하기!)

 

 

해결 방법

👀 작은 부분 문제를 해결하고 전체 문제를 해결하는 DP(Dynamic Programming)을 사용하였습니다. tab라는 저장 배열을 만들어주고 결과를 저장하며 업데이트하는 방식으로 구현했습니다.Bottom-UP

1. tab : 배열 arr의 최대합을 저장하는 배열으로, 0으로 초기화
2. 외부 반복문(i) : 1부터 n까지
  - i : 배열 arr의 인덱스, tab[i] : arr[0]부터 arr[i-1] 까지의 최대합
  - 부분 배열의 끝이 'i-1' 번째 요소이기 때문에, i는 부분 배열의 마지막 요소 다음 위치를 가리킴
3. 내부 반복분(j) :  1부터 min(k, i) 까지 
  - j : 현재 위치 'i' 에서 길이 'j'인 부분 배열 고려
  - i-j : 부분 배열의 시작 인덱스
4. 부분 배열 최대값 max_val
5. 부분 배열을 최대값으로 변경
6. 최대합 tab 업데이트

 

시간복잡도 O(n*k)

• 외부 반복문 n 번, 내부 반복문 최대 k 번
• 공간 복잡도 O(n)
  • 크기 n+1인 배열 tab 사용

---

✔ Answer

class Solution:
    def maxSumAfterPartitioning(self, arr: List[int], k: int) -> int:
        n = len(arr)
        # DP table 초기화
        tab = [0]* (n+1)
        
        for i in range(1, n+1):
            max_val = 0
            # tabulation
            for j in range(1, min(k,i) +1):
                max_val = max(max_val, arr[i-j])
                tab[i] = max(tab[i], tab[i-j] + max_val * j)
                
        return tab[n]

---

💬 소감

코드는 짧은듯하지만 배열의 관계를 생각하는 부분에 있어서 오래걸렸던 문제였습니다. 집중 필요!