문제 이해하기
숫자로 이루어진 배열 A가 주어졌을 때, 이를 최대 K개의 인접한 그룹으로 분할한다고 가정해 보겠습니다. 이때 점수는 각 그룹의 평균값들의 합으로 정의되며, 우리의 목표는 얻을 수 있는 가장 큰 점수를 찾는 것입니다.
예를 들어 A = [9,1,2,3,9]이고 K = 3이라면 결과는 20이 됩니다. 가장 좋은 선택은 A를 [9], [1, 2, 3], [9]로 나누는 것이기 때문입니다. 따라서 답은 다음과 같습니다.
9 + (1 + 2 + 3) / 3 + 9 = 20
물론 [9, 1], [2], [3, 9]처럼 나누는 방법도 가능하지만, 이 경우에는 더 작은 점수가 나오게 됩니다.
접근 방법: 동적 계획법(DP)
이 문제는 재귀 호출과 메모이제이션을 결합한 동적 계획법으로 효율적으로 해결할 수 있습니다. 해결 단계는 다음과 같습니다.
- 메모이제이션을 위한 2차원 행렬 dp를 정의합니다.
- 배열 A, 현재 인덱스, 남은 그룹 수 k를 매개변수로 받는 재귀 함수 solve()를 정의합니다.
- 인덱스가 배열 A의 크기 이상이면 0을 반환합니다. (나눌 요소가 더 이상 없음)
- k가 0이면 -100000을 반환합니다. (요소가 남았는데 그룹 개수를 모두 소진한 경우)
- dp[index][k]의 값이 -1이 아니라면 이미 계산된 값이므로 그대로 반환하여 중복 연산을 방지합니다.
- ret := -무한대, sum := 0으로 초기화합니다.
- i가 index부터 배열 A의 크기 - 1까지 반복합니다.
- sum에 A[i]를 누적합니다.
- ret을 'sum / (i - index + 1) + solve(A, i + 1, k - 1)'와 ret 중 더 큰 값으로 갱신합니다.
- 계산 결과를 dp[index][k]에 저장한 뒤 반환합니다.
메인 함수에서는 다음과 같이 처리합니다.
- n := 배열 A의 크기
- dp := n × (K + 1) 크기의 행렬을 생성하고 모든 값을 -1로 초기화
- solve(A, 0, K)를 호출하여 결과 반환
C++ 코드 구현
아래 예제 코드를 통해 더 자세히 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector < vector <double> > dp;
double solve(vector <int>& A, int idx, int k){
if(idx >= A.size()) return 0;
if(!k) return -100000;
if(dp[idx][k] != -1) return dp[idx][k];
double ret = INT_MIN;
double sum = 0;
for(int i = idx; i < A.size(); i++){
sum += A[i];
ret = max(sum / (i - idx + 1) + solve(A, i + 1, k - 1), ret);
}
return dp[idx][k] = ret;
}
double largestSumOfAverages(vector<int>& A, int K) {
int n = A.size();
dp = vector < vector <double> > (n, vector <double>(K + 1, -1));
return solve(A, 0, K);
}
};
main(){
vector<int> v = {9,1,2,3,9};
Solution ob;
cout << (ob.largestSumOfAverages(v, 3));
}
입력
[9,1,2,3,9] 3
출력
20
마무리
이 풀이의 시간 복잡도는 O(n² × K)이며, 공간 복잡도는 O(n × K)입니다. 재귀 호출 시마다 가능한 모든 분할 지점을 탐색하지만, dp 테이블을 활용해 이미 계산한 상태를 재사용함으로써 불필요한 중복 계산을 제거할 수 있습니다. 이러한 메모이제이션 기법은 배열을 여러 부분으로 나누어 최적화하는 유형의 문제에서 널리 활용되므로, 잘 익혀두면 다양한 DP 문제 해결에 도움이 됩니다.