백준 16494, 가장 큰 값

개요

문제 링크
골드 5, DP
M개의 부분집합의 총 합의 최댓값

---

접근

2228번과 거의 완벽히 동일하다. 부분집합이 연속하지 않기 때문에 for문의 범위가 약간 달라지는 것빼고는 코드까지 동일하다. 따라서 접근은 2228번으로 대체한다.

---

Pseudo code

dp[i][k] = 끝이 i이고 k개 집합을 쓴 최대 합
for(k = 집합 사용개수)
    for (j = i의 앞 = k-1개 사용한 부분)
        for (r = j의 뒤 i의 앞 = 부분합을 구할 부분)
            if (j까지 k-1개 사용 + sum[r~i]가 더 작으면)
                업데이트

---

Source code

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    int a[n];
    int sum[n][n];
    for (int i=0; i<n; i++) {
        cin >> a[i];
        sum[i][i] = a[i];
    }
    for (int i=1; i<n; i++)
        for (int j=0; j<i; j++)
            sum[j][i] = sum[j][i-1]+a[i];

    int dp[n][m+1];
    for (int i=0; i<n; i++)
        for (int j=1; j<=m; j++)
            dp[i][j] = -2e9;
    for (int i=0; i<n; i++)
        for (int j=0; j<=i; j++)
            dp[i][1] = max(dp[i][1], sum[j][i]);
    for (int k=2; k<=m; k++)
        for (int i=0; i<n; i++)
            for (int j=0; j<i; j++)
                for (int r=j+1; r<=i; r++)
                    dp[i][k] = max(dp[i][k], dp[j][k-1]+sum[r][i]);
    int ans = -2e9;
    for (int i=0; i<n; i++)
        ans = max(ans, dp[i][m]);
    cout << ans;
}