BOJ 2228 - 구간나누기 (dp)

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

 

<문제설명>

최대 100자의 숫자배열을 입력 받았을 때 연속된 수열을 총 m개 뽑을 때 그 뽑힌 숫자들의 최대값을 구하는 문제.

 

<풀이>

**dp값을 처음 초기화 할 때 특정 값으로 초기화 하기가 애매하다. 숫자가 음수일 수 있기 때문. 따라서 bool타입 c[101][51]을 사용해서 지금 상태가 이미 메모된 상태인지 기록해둔다.

(psum 사용하므로 1-base )

 

 

f(i, j) : 1 ~ i 번째 숫자를 사용하여 j개의 연속된 수열을 뽑을 때 뽑힌 숫자들의 최댓값

f(i, j) = max(i번째 숫자를 뽑지 않을 때, i번째 숫자를 뽑을 때)

 

1. i번째 숫자를 뽑지 않는 경우 f(i,j) = f(i-1, j)

 

2. k번째 ~ i번째 숫자를 뽑는 경우 f(i,j) = psum(k,i) + f(k-2, j-1)  -- (1 <= k <= i 중 최대가 되도록) 

 

3. 기저 처리

j==0인 경우 모두 뽑은 상태이므로 0 반환

 

k<=0 인 경우 불가능한 상황. -1e9 반환

 

<코드>

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int IMP = -1e9;

int n, m, dp[101][51], a[102], psum[102];
bool c[101][51];

int f(int k, int cnt) {
	if (cnt == 0) return 0;
	if (k <= 0) return IMP;

	if (c[k][cnt]) return dp[k][cnt];
	c[k][cnt] = true;

	int& ret = dp[k][cnt];
	
	ret = f(k-1,cnt);
	for (int i = 1; i <= k; i++)
		ret = max(f(i - 2, cnt - 1) + psum[k] - psum[i - 1], ret);

	return ret;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		psum[i] = psum[i - 1] + a[i];
	}

	memset(c, false, sizeof(c));

	cout << f(n, m) << '\n';
}