백준 2228 : 구간 나누기

 

간단한 DP문제이다.

 

Dp[i][j]를 "i개의 그룹으로 j까지 구간을 나누었을때 만들 수 있는 최댓값"으로 정의한 뒤에 풀면 쉽게 풀 수 있다.

n범위가 100으로 작은 편이기에 3중 for문을 이용해도 된다.

따라서,

0~j - 2구간을 탐색하는 k를 이용하면 풀 수 있다.

(0~k까지의 구간을 i - 1개로 나누었을 때 만들 수 있는 최댓값) + (k~j의 원소의 합)

중 최댓값이

Dp[i][j]의 값이다.

 

문제의 조건을 주의하자.

나는 배열의 크기를 반대로 잡아서 한참을 고민했다.

 

Code

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

int n, m;
ll arr[110];
ll dp[110][110], sum[110];

int main()
{
    int i, j;
    scanf("%d %d", &n, &m);
    for(i=1;i<=n;i++) {
        scanf("%lld", &arr[i]);
        sum[i] = sum[i - 1] + arr[i];
    }
    for(i=1;i<=m;i++) {
        for(j=0;j<=n;j++) {
            dp[i][j] = -2e9;
        }
    }
    dp[1][1] = arr[1];
    for(i=2;i<=n;i++) {
        dp[1][i] = max(dp[1][i - 1] + arr[i], arr[i]);
    }
    for(i=1;i<=n;i++) {
        for(j=1;j<=i;j++) 
            dp[1][i] = max(dp[1][j], dp[1][i]);
    }
    for(i=2;i<=m;i++) {
        for(j=2;j<=n;j++) {
            dp[i][j] = dp[i][j - 1];
            for(int k=0;k<=j - 2;k++) {
                dp[i][j] = max(dp[i][j], dp[i - 1][k] + sum[j] - sum[k + 1]);
            }
        }
    }
    printf("%lld", dp[m][n]);
    return 0;
}

 

문제링크

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