[BAEKJOON] 2228번 구간 나누기

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

2228번: 구간 나누기

문제조건

1. 각 구간은 한개이상의 연속된 수로 이뤄짐
2. 서로다른 두 구간은 겹쳐있거나, 인접하면 안됨
3. 정확히 M개의 구간이어야함

뭔가 좀처럼 접근방법이 떠오르지 않았다.

계속해서 경우의수가 다르기 때문에 DFS로 완전탐색을 돌려야하나 ,,? 

어떻게 풀지 감이안와서 접근 방법만 찾아봤다. 역시 dynamic programming,,, 왠지 감이 안잡힌다 생각했다.

식을 세워야하는데 여기서 보통 dp로 풀때처럼 시작점과 끝점을 인덱스로 잡아버리면 M개의 구간에 대해서의 등식이 성립할수 없다. 따라서 나는 dp[n][m] : n번째까지 , m개의 구간 중 합의 최대값 으로 설정했다.

인접할 수 없다는 말에서 구간끼리 한칸이상은 떨어져야 한다는 것을 알았는데, 말이 되게 어렵다,,

• i번째 수를 택하지 않는 경우: 이 경우 i - 1번째와 값이 같아진다.

점화식은

dp[i][j] = dp[i - 1][j] 가 된다.

• i번째 수를 택할 경우: 각 구간은 인접할 수 없으므로 1번째부터 i - 2번째 사이에서 j - 1개의 구간을 선택한 값과 k번째(선택한 값)에서 i번째까지의 구간합을 더한 값 중에서 최대값을 가져와야 한다.

점화식으로 표현하면

dp[i][j] = dp[i - 2][j - 1] + prefixsum[i] - prefixsum[k - 1] 꼴로 나타낼 수 있다.

#include <iostream>
#include <vector>
#define MIN -3276800
using namespace std;

//dp[n][m] : n번째까지 , m개의 구간 중 합의 최대값
int n, m, dp[101][52], sum[101];

int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		//누적합 구하기
		sum[i] = a + sum[i - 1];
	}
	for (int i = 1; i <= m; i++) dp[0][i] = MIN;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			//i번째 수를 택하지 않는 경우
			dp[i][j] = dp[i - 1][j];
			//i번째 수를 택할 경우
			for (int k = 1; k <= i; k++) {
				if (k == 1 && j == 1) dp[i][j] = max(dp[i][j], sum[i]);
				else if (k >= 2) dp[i][j] = max(dp[i][j], dp[k - 2][j - 1] + sum[i] - sum[k - 1]);
			}
		}
	}
	cout << dp[n][m];
}

문제를 이해하는데 많은 시간이 걸렸다,,,