[99클럽] 99클럽 코테 스터디 20일차 TIL - 동적계획법 (Dynamic Programming)

 

오늘의 문제

LeetCode - Partition Array for Maximum Sum (출처 하단 표기)

비기너 문제가 쉬워서 미들러 문제도 같이 풀어보았다.

 

문제

Given an integer array arr, partition the array into (contiguous) subarrays of length at most k. After partitioning, each subarray has their values changed to become the maximum value of that subarray.

Return the largest sum of the given array after partitioning. Test cases are generated so that the answer fits in a 32-bit integer.

 

제한사항

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^9
• 1 <= k <= arr.length

입출력 예

arr	k	return
[1,15,7,9,2,5,10]	3	84
[1,4,1,5,7,3,6,1,9,9,3]	4	83
[1]	1	1

 

풀이

import java.util.*;

class Solution {
    public int maxSumAfterPartitioning(int[] arr, int k) {
        int n = arr.length;
        int[] dp = new int[n+1];  // dp[i] = arr[0]부터 arr[i-1]까지의 최대 합 저장
        
        for (int i=1; i<=n; i++) {
            int subMax = 0;
            for (int j=1; j<=k && i-j>=0; j++) {
                subMax = Math.max(subMax, arr[i-j]);    // i부터 j개까지의 최대 원소
                dp[i] = Math.max(dp[i], dp[i-j] + subMax * j); // i부터 j까지의 최대 합
            }
        }
        
        return dp[n];
    }
}

 

주어진 배열에서 최대 k개로 부분 배열을 만든 후 각 서브 배열을 최댓값으로 바꾼 후 그 수의 합을 구하는 문제였다. 배열을 정렬하지 않고 최대합을 찾는 문제이기 때문에 DP를 이용하는 것이 좋을 것 같다고 생각했다. 원소의 최대 합을 저장할 배열을 선언한 후, arr 배열을 순회하면서 i부터 최대 k개를 뽑아 가장 큰 값을 찾은 후 dp 배열에 최대 합을 저장하는 형식으로 작성하였다. dp 배열의 끝 값이 최대합임으로 이를 return 해주면 된다. 처음에 풀 때 k개만큼 서브 배열이 구성되지 않는 경우를 생각하지 못해 힌트를 보고 풀었다.

 

 

출처: LeetCode, https://leetcode.com/problems/partition-array-for-maximum-sum/