[BOJ] 2228 - 구간 나누기 (C++)

문제

구간 나누기

코드

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

#define MIN -3276800

int arr[101] = {0}, dp[101][51] = {0};
int N, M;

int solve(int n, int m){
    if (m == 0) return 0;
    if (n <= 0) return MIN;
    if (dp[n][m] != -1) return dp[n][m];

    int sum = 0;
    dp[n][m] = solve(n-1, m);
    for (int i = n; i > 0; i--){
        sum += arr[i];
        int temp = solve(i-2, m-1) + sum;
        dp[n][m] = max(dp[n][m], temp);
    }
    return dp[n][m];
}

int main(void){
    cin.tie(0); 
    ios_base::sync_with_stdio(false);
    
    cin >> N >> M;
    memset(dp, -1, sizeof(dp));
    
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    
    cout << solve(N, M);
    
    return 0;
}

접근

예제의 결과는 -1 (3) 1 (2 4) -1 다음과 같이 구간을 나누어 결과가 9가 된 것이다. 구간을 나누고 합이 최대가 되어야 하기 때문에 이전 값들을 저장하고 이용해야 될 것 같은 기분이 들었다. 그래서 2차원 배열 dp를 사용하였다.

dp[i][j] : 1~i 번째 인덱스까지의 배열에서 j개의 구간을 선택했을 때 구간합의 최대 값

재귀 함수에서는 n번째 인덱스를 제외한 이전 인덱스까지의 경우의 수를 재귀 함수로 계산한 뒤에 i~n 구간까지의 누적 합을 구하고 인접하지 않는 구간 범위에서 m-1 개의 구간 합을 구하는 식으로 진행한다.