[백준] 2228번: 구간 나누기

📌 문제

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

📌 설명

배열의 누적 합을 구하고, m개의 구간을 선택하며 구간 합의 최대값을 구하는 문제이다.

📌 코드

#include <iostream>
#include <algorithm>

#define INF 3276701

using namespace std;

int cumsum[101]; // cumsum[i]: i번째 원소까지 누적 합
int dp[101][51]; // dp[i][j]: 0부터 i-1까지의 배열 중 j개 구간 합의 최대값
int arr[100];

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cumsum[0] = 0;
    for (int i = 1; i <= n; i++) {
        cumsum[i] = cumsum[i - 1] + arr[i - 1];
    }

    // dp 초기화
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j] = -INF;
        }
        // 선택한 구간이 0개인 경우
        dp[i][0] = 0;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= min(m, (i + 1) / 2); j++) {
            // i번째 원소를 선택하지 않는 경우
            dp[i][j] = dp[i - 1][j];

            // i번째 원소를 누적 합에 포함시키는 경우
            for (int k = 1; k <= i; k++) {
                // k번째부터 i번째까지 누적 합
                int k2i = cumsum[i] - cumsum[k - 1];

                // 첫 번째 구간인 경우
                if (j == 1) {
                    dp[i][j] = max(dp[i][j], k2i);
                }
                else if (k >= 2) {
                    dp[i][j] = max(dp[i][j], dp[k - 2][j - 1] + k2i);
                }
            }
        }
    }

    cout << dp[n][m];
}

---

// dp 초기화
for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= m; j++) {
        dp[i][j] = -INF;
    }
    // 선택한 구간이 0개인 경우
    dp[i][0] = 0;
}

배열의 값은 음수가 가능하며, 이후 dp 배열을 초기화할 때 max 함수를 사용하므로 음의 무한대로 dp 배열의 초기값을 세팅한다.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= min(m, (i + 1) / 2); j++) {
        // i번째 원소를 선택하지 않는 경우
        dp[i][j] = dp[i - 1][j];

        // i번째 원소를 누적 합에 포함시키는 경우
        for (int k = 1; k <= i; k++) {
            // k번째부터 i번째까지 누적 합
            int k2i = cumsum[i] - cumsum[k - 1];

            // 첫 번째 구간인 경우
            if (j == 1) {
                dp[i][j] = max(dp[i][j], k2i);
            }
            else if (k >= 2) {
                dp[i][j] = max(dp[i][j], dp[k - 2][j - 1] + k2i);
            }
        }
    }
}

1번째 원소부터 i번째 까지 구간의 합을 구할 때, i번째 원소를 반드시 포함할 필요는 없다. 포함하지 않는다면 이전 dp 배열 값으로 현재 dp 배열을 초기화한다: dp[i][j] = dp[i - 1][j];

구간 합에 i번째 원소를 포함시키는 경우 점화식은 다음과 같다. dp[i][j] = max(dp[i][j], dp[k - 2][j - 1] + k2i); k2i 는 k번째 원소부터 i번째 원소까지의 누적 합이다. 점화식을 해석하면 다음과 같다. ‘i번째 원소까지 j개의 구간 합의 최대값은 dp[i][j]와 k - 2번째 원소까지 j - 1개의 구간 합의 최대값에 k번째 원소부터 i번째 원소까지의 누적합의 합 중 최대값이다.’

---

시간복잡도는 3중 for문에서 결정된다. 1차 for문에서 $O(n)$, 2차 for문에서 $O(m)$, 3차 for문에서 $O(n)$의 연산을 수행하는 것으로 간주할 수 있다. 따라서 전체 시간복잡도는 $O(n^2 \cdot m)$이다.

공간복잡도는 dp 배열에 의해 결정되며, $O(nm)$이다.