[BAE/<JOON> 문제풀이] 2228. 구간 나누기

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

2228번: 구간 나누기

서론

DP 문제를 모르겠으면 DP 테이블 배열에 들어갈 요소 무조건 정하고 억지로라도 점화식 만들어 수정하는게 나은 것 같다.

그렇게 해야 최소한 풀이 힌트 건덕지라도 나온다.

풀이

우선 복수의 구간 없이 단일 구간 합의 최대를 구하는 알고리즘을 생각해보자.

점화식은 dp[i] = max(dp[i - 1] + arr[i], arr[i]) 이다.

문제에서 구하는 답은 서로 인접하거나 겹치지 않는 복수의 구간 에 해당하는 구간의 최댓값이므로 DP 테이블에

현재 구간 수 라는 요소가 추가되어야 할 것이다.

그 다음으로 생각할 것은 1개 이상의 나눠진 구간들에 대한 점화식을 떠올리는 것이다.

서로 다른 두 구간은 인접할 수 없으므로 구간수 j-1개로 이루어져있으며 인덱스는 i-2 지점까지가 최대다.

즉, 점화식은 dp[i][j] = max(dp[1~i-2][j-1], dp[i-1][j]) + arr[i] 이다.

여기서 왜 1~i-2 구간을 확인하냐면 단일 구간에 대한 점화식은 현재인덱스 i를 포함하는 구간 의 최댓값이기 때문에

dp[i]가 전체 구간에 대한 최적값이 아니기 때문이다. 전체 구간은 1~n을 순회하며 최댓값을 따로 찾아야한다.

그렇기 때문에 j-1 구간의 합의 최댓값도 1~i-2 구간을 탐색해서 따로 최댓값을 찾아야한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	int n, m; cin >> n >> m; vector<int> arr(n + 1), ps(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> arr[i]; ps[i] = ps[i - 1] + arr[i];
	}
	vector<vector<int>> dp(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= m; i++) {
		for (int j = 0; j <= i * 2; j++) {
			dp[j][i] = -2100000000;
		}
	}
	for (int i = 1; i <= n; i++) {
		dp[i][1] = dp[i - 1][1] + arr[i] > arr[i] ? dp[i - 1][1] + arr[i] : arr[i];
		if (i < 3) continue;
		for (int j = 2; j <= m; j++) {
			dp[i][j] = -2100000000;
			for (int k = 1; k <= i - 2; k++) {
				int s1 = dp[k][j - 1] + arr[i] > dp[i - 1][j] + arr[i] ? dp[k][j - 1] + arr[i] : dp[i - 1][j] + arr[i];				
				dp[i][j] = dp[i][j] > s1 ? dp[i][j] : s1;
			}
		}
	}
	int mx = -2100000000; 
	for (int i = 1; i <= n; i++) {
		mx = mx > dp[i][m] ? mx : dp[i][m];
	}
	cout << mx << "\n";
	/*for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			cout << dp[j][i] << " ";
		}
		cout << "\n";
	}*/
	return 0;
}