문제 소개
양의 정수로 이루어진 배열과 하나의 값 m이 주어졌다고 가정해 봅시다. 우리는 이 배열을 m개의 연속된 부분 배열로 나눌 수 있으며, 나눠진 부분 배열들 중 가장 큰 합이 최소가 되도록 만드는 알고리즘을 설계해야 합니다.
예를 들어 배열이 [7, 2, 4, 10, 9]이고 m = 2라고 가정해 보겠습니다. 이 경우 배열을 [7, 2, 4](합 13)와 [10, 9](합 19)의 두 부분 배열로 나눌 수 있으며, 이때 가장 큰 합을 가지는 부분 배열의 합은 19입니다. 어떤 방식으로 나누더라도 이 값보다 작아질 수 없으므로 정답은 19가 됩니다.
풀이 접근 방식: 동적 계획법(DP)
이 문제는 동적 계획법(Dynamic Programming)을 활용해 단계별로 해결할 수 있습니다. 절차는 다음과 같습니다.
- splitArray() 함수를 정의합니다. 이 함수는 배열 v와 정수 m을 매개변수로 받습니다.
- n := 배열 v의 크기
- 크기가 n인 dp 배열을 생성합니다.
- 크기가 n인 누적 합(sum) 배열을 생성합니다.
- sum[0] := v[0]
- i를 1부터 n-1까지 증가시키며 반복:
- sum[i] := sum[i - 1] + v[i]
- dp[0] := sum[n - 1]
- i를 1부터 n-1까지 증가시키며 반복:
- dp[i] := sum[n - 1] - sum[i - 1]
- i를 1부터 m-1까지 증가시키며 반복:
- start를 0부터 n-i-1까지 증가시키며 반복:
- end를 start+1부터 n-i까지 증가시키며 반복:
- dp[start] := min(dp[start], max(start == 0 ? sum[end - 1] : sum[end - 1] - sum[start - 1], dp[end]))
- start를 0부터 n-i-1까지 증가시키며 반복:
- dp[0]을 반환합니다.
동작 원리
여기서 dp[i]는 "인덱스 i부터 배열 끝까지를 남은 횟수만큼 분할할 때, 가장 큰 부분 배열 합의 최솟값"을 의미합니다. 초기 상태에서는 분할을 고려하지 않고 배열 전체를 한 덩어리로 보므로, dp[i]는 i부터 끝까지의 구간 합으로 설정됩니다. 이후 분할 횟수를 하나씩 늘려가면서, 각 시작 위치(start)마다 가능한 모든 분할 지점(end)을 시도합니다. 현재 구간의 합과 나머지 부분의 최적해(dp[end]) 중 더 큰 값을 후보로 삼고, 그중 가장 작은 값을 선택하며 답을 갱신하는 방식입니다.
그럼 실제 구현 예제를 통해 더 자세히 살펴보겠습니다.
구현 예제 (C++)
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int splitArray(vector<int>& v, int m) {
int n = v.size();
vector <long long int > dp(n);
vector <long long int> sum(n);
sum[0] = v[0];
for(int i =1;i<n;i++)sum[i] =sum[i-1]+v[i];
dp[0] = sum[n-1];
for(int i =1;i<n;i++){
dp[i] = sum[n-1] - sum[i-1];
}
for(int i =1;i<m;i++){
for(int start = 0;start<n-i;start++){
for(int end = start+1;end<=n-i;end++){
dp[start] = min(dp[start],max((start==0?sum[end-1]:sum[end-1]-sum[start-1]),dp[end]));
}
}
}
return dp[0];
}
};
main(){
Solution ob;
vector<int> v = {7,2,4,10,9};
cout << (ob.splitArray(v, 2));
}입력
[7,2,4,10,9] 2
출력
19
복잡도 분석
세 겹의 반복문을 사용하기 때문에 이 알고리즘의 시간 복잡도는 O(m × n²)이며, dp 배열과 sum 배열을 위해 추가 공간이 필요하므로 공간 복잡도는 O(n)입니다.