BOJ 2228 - 구간 나누기(DP) - tabulation, memoization

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

2228번: 구간 나누기

- 한 칸씩 넘어가면서 각 원소를 구간에 포함한 경우, 포함하지 않은 경우로 나눠서 최대합을 구하는 방식으로 풀었다.
어느 지점 i까지 구간에 포함하여 합을 구하였을 때 그 다음 구간에 추가하려면 i + 2부터 추가를 해야된다(구간이 연속되면 안된다)
i 지점까지 사용한 구간의 갯수가 똑같다면 i + 2지점 이후로는 i지점까지 구한 최대합에 추가로 더해줘야하는 별개의 문제가 된다(subproblem이 된다). 

- 따라서 어느 지점(고려한 지점), 선택한 구간의 갯수, 포함했는지 여부, 이 지점까지의 합이 상태값이 되며 이를 이용해서 점화식을 세울 수 있다. 

 

// 바텀업 tabulation
#include <cstring>
#include <iostream>
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)
using namespace std;

int n, m, a[101], d[101][101][2]; // d[i][j][k] = i번째 숫자를 j번쨰 구간에 k(이용안한다, 한다)

int main() {
    FASTIO;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    memset(d, -32768 * 100, sizeof(d));
    for (int i = 0; i <= n; ++i) {
        d[i][0][0] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            d[i][j][0] = max(d[i - 1][j][0], d[i - 1][j][1]); // i번째 숫자를 j번째 범위에 포함안함
            d[i][j][1] = max(d[i - 1][j - 1][0] + a[i], d[i - 1][j][1] + a[i]); // 포함함
        }
    }

    cout << max(d[n][m][0], d[n][m][1]);
    return 0;
}

// top-down, memoization

#include <iostream>
#include <cstring>
using namespace std;
#define FASTIO cin.tie(nullptr)->sync_with_stdio(false)

int n, m, a[101], d[101][101], psum[101];

int go(int n, int m) { // idx, group
    if (m == 0) return 0;
    if (n <= 0) return -32768 * 100;

    int &ret = d[n][m];
    if (ret != -1) return ret;

    ret = go(n - 1, m);
    for (int k = n; k >= 1; --k) {
        ret = max(ret, go(k - 2, m - 1) + psum[n] - psum[k] + a[k]);
    }
    return ret;
}

int main() {
    FASTIO;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        psum[i] = psum[i - 1] + a[i];
    }
    memset(d, -1, sizeof(d));
    cout << go(n, m);
    return 0;
}

- k ~ n까지의 부분합을 미리 구해놓고 연산해서 썼다.