정수 배열 A가 주어졌을 때, 이 배열을 길이가 최대 K 이하인 연속된 부분 배열로 분할해야 합니다. 분할이 끝나면 각 부분 배열에 속한 모든 값은 해당 부분 배열의 최댓값으로 변경됩니다. 우리가 구해야 하는 것은 분할 후 배열에서 얻을 수 있는 가장 큰 합입니다.
예를 들어 입력이 [1, 15, 7, 9, 2, 5, 10]이고 k = 3이라면 출력은 84가 됩니다. 그 이유는 배열이 [15, 15, 15, 9, 10, 10, 10]으로 변경되기 때문입니다. 첫 세 요소(1, 15, 7)는 하나의 그룹으로 묶여 각각 15가 되고, 마지막 세 요소(2, 5, 10)는 묶여 각각 10이 되는 방식입니다.
문제 해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. dp[i]는 '처음 i+1개의 원소까지 고려했을 때 얻을 수 있는 최대 합'을 의미합니다. 각 위치에서 마지막 그룹의 길이를 1부터 K까지 시도해 보며 최댓값을 갱신하는 것이 핵심 아이디어입니다.
단계별 알고리즘은 다음과 같습니다.
- A와 같은 길이의 dp 배열을 만들고 0으로 초기화합니다.
- i를 0부터 (A의 길이 - 1)까지 반복합니다.
- i - 1 >= 0이면 dp[i] = A[i] + dp[i - 1], 그렇지 않으면 dp[i] = A[i]로 설정합니다.
- temp := A[i]로 초기화합니다(현재 구간의 최댓값 후보).
- j를 1부터 (k - 1)까지 반복합니다.
- i - j >= 0인 경우:
- index := i - j
- temp := temp와 A[i - j] 중 더 큰 값으로 갱신
- index - 1 >= 0이면, dp[i] := dp[i]와 (temp × (i - index + 1) + dp[index - 1]) 중 더 큰 값
- 그렇지 않으면 dp[i] := dp[i]와 0 중 더 큰 값
- i - j >= 0인 경우:
- dp 배열의 마지막 원소를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 동작 과정을 더 쉽게 이해할 수 있습니다.
class Solution(object):
def maxSumAfterPartitioning(self, A, K):
dp = [0 for i in range(len(A))]
for i in range(len(A)):
dp[i] = A[i] + (dp[i-1] if i-1>=0 else 0)
temp = A[i]
for j in range(1,K):
if i-j>=0:
index = i-j
temp = max(temp,A[i-j])
dp[i] = max(dp[i],temp*(i-index+1) + (dp[index-1] if index-1 >=0 else 0))
return dp[-1]
ob = Solution()
print(ob.maxSumAfterPartitioning([1,15,7,9,2,5,10],3))입력
[1,15,7,9,2,5,10] 3
출력
84
복잡도 분석
배열의 각 원소마다 최대 K개의 그룹 길이를 검사하므로 시간 복잡도는 O(N×K)이며, dp 배열을 위해 O(N)의 추가 공간이 필요합니다. 완전 탐색으로는 지수 시간이 걸리는 문제를 다항 시간 안에 해결할 수 있어 실용적인 접근 방식입니다.