[백준 2228] 구간 나누기

문제

백준 2228

유형

• DP

풀이

일단 테이블(dp[i][j])을 i개의 배열로 j개의 구간을 선택했을 때 최대 값이라고 설정하였다.

그럼 dp[i][j]가 되는 경우는 i번째를 포함하지 않으면서 j개의 구간을 선택했을 때와 i번째를 포함하면서 j-1번째 구간이 i-2를 넘지 않는 경우 중 가장 큰 값을 선택하면 된다.

그래서 점화식은
dp[i][j] = max(dp[i-1][j], max(dp[k-2][j-1] + sum[i] - sum[k-1])(k: 1~i))

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
int sum[101];
int dp[101][51];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		sum[i] = x + sum[i - 1];
	}

	for (int j = 1; j <= m; j++) {
		dp[0][j] = -3276800;
	}

	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			dp[i][j] = dp[i - 1][j];
			for (int k = 1; k <= i; k++) {
				if (k >= 2)
					dp[i][j] = max(dp[i][j], dp[k - 2][j - 1] + sum[i] - sum[k - 1]);
				else if (k == 1 && j == 1)
					dp[i][j] = max(dp[i][j], sum[i]);
			}
		}
	}

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