2228번(다시..)

2228번 - 구간 나누기

처음에 나는 맨 마지막 값을 선택한다, 안한다까지는 맞췄지만,

선택할 때, 맨 마지막 값을 그룹으로 처리하는 방법 까지는 생각 못했었다.

그룹으로 처리하면 점화식은 쉽게 나왔다.

D[N][M] = max( D[N-1][M] , D[k-1][M-1] + v[k] +... + v[N-1] )

즉 D[N][M] 은 N개에서 M그룹을 만들 때 최대값.

문제를 풀긴 했는데, 뭔가 기저 조건이 찜찜하게 느껴진다...

아직 완벽하게 내 문제로 소화하지 못한 것 같다 다시 풀어 봐야지

<정답 코드>

#include<iostream>
#include<vector>
#include<string.h>
#include<algorithm>
using namespace std;
int N, M;
vector<int> v;
int D[101][101];
bool check[101][101];
const int no = -987654321;
int go(int n, int m)
{
    if (m == 0)
    {
        return 0;
    }
 
    if (n <= 0)
    {
        return no;
    }
    
    
    if (check[n][m])
    {
        return D[n][m];
    }
 
    check[n][m] = true;
    D[n][m] = go(n - 1, m);
 
    for (int k = n - 1; k >= 0; k--)
    {
        int sum = 0;
        for (int j = n - 1; j >= k; j--)
        {
            sum += v[j];
        }
        D[n][m] = max(D[n][m], go(k - 1, m - 1) + sum);
    }
 
    return D[n][m];
}
int main()
{
    scanf("%d %d", &N, &M);
    v.resize(N);
    for (int i = 0; i < 101; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            D[i][j] = no;
        }
    }
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &v[i]);
    }
 
    printf("%d\n", go(N, M));
    
    return 0;
}