취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2228번 문제인 구간 나누기이다.
문제는 아래 링크를 확인하자.

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

구간 [1,i]에서 정확히 k개의 구간을 선택하는 경우는 (i번째 원소가 구간에 포함되어있는 경우)와 (i번째 원소가 구간에 포함되어있지 않은 경우)로 구분할 수 있다. 이 두 경우를 이용해 점화식을 세워 dp로 문제를 해결하자.

아래는 제출한 소스코드이다:

#include <iostream>
using namespace std;

int N, M;
int arr[101];
int dp1[101][101]; // [i][k]: i번째 수까지 확인함, 구간 k개, 마지막 구간이 i번째 수를 포함
int dp2[101][101]; // [i][k]: i번째 수까지 확인함, 구간 k개, 마지막 구간이 i번째 수를 미포함

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) cin >> arr[i];
	for (int i = 1; i <= N; i++) {
		for (int k = (i + 1) / 2; k > 0; k--) {
			if (i / 2 < k) dp1[i][k] = dp2[i - 1][k - 1] + arr[i];
			else dp1[i][k] = max(dp1[i - 1][k] + arr[i], dp2[i - 1][k - 1] + arr[i]);
			if (i / 2 < k) dp2[i][k] = -1000000007;
			else dp2[i][k] = max(dp1[i - 1][k], dp2[i - 1][k]);
		}
	}

	cout << max(dp1[N][M], dp2[N][M]);
}