[BOJ] 16494 가장 큰 값

문제

16494번: 가장 큰 값

N개의 정수로 이루어진 수열이 주어진다. 주어진 수열에서 연속된 1개 이상의 수로 이루어진 부분 수열을 "그룹"이라고 하자. 양의 정수 M이 주어졌을 때 M개의 그룹을 선택해서 그룹에 속한 모든 수의 합의 최댓값을 구하는 프로그램을 작성하라.

https://www.acmicpc.net/problem/16494

풀이

코드

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> pii;
 
int n, m, ans = -1e9;
int arr[20];
int vis[20];
vector<pii> v;
 
int sm() {
    int ret = 0;
    for(int i = 0; i < m; i++) {
        int l = v[i].first, r = v[i].second;
        for(int j = l; j <= r; j++) ret += arr[j];
    }
    return ret;
}
 
void go(int ix) {
    if (v.size() == m) {
        ans = max(ans, sm());
    } else {
        int l;
        for(int i = ix; i < n; i++) {
            if (vis[i]) continue;
            vis[i] = 1;
            l = i;
            for(int j = l; j < n; j++) {
                if (vis[j] and j != i) break;
                vis[j] = 1;
                v.push_back({l, j});
                go(j);
 
                vis[j] = 0;
                v.pop_back();
            }
            vis[i] = 0;
        }
    }
}
 
int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
    go(0);
    printf("%d", ans);
}

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n, m;
int arr[20];
int dp[20][20];
 
int go(int ix, int cnt) {
    if (cnt == m) return 0;
    if (ix == n) return -1e9;
    if (dp[ix][cnt] != -1) return dp[ix][cnt];
    int ret = go(ix + 1, cnt), t = 0;
    for(int i = ix; i < n; i++) {
        t += arr[i];
        ret = max(ret, go(i+1, cnt + 1) + t);
    }
    return dp[ix][cnt] = ret;
}
 
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", &arr[i]);
    printf("%d", go(0, 0));
}