2228 구간 나누기

다이나믹 프로그래밍으로 해결해야 하는 knapsack 계열의 문제이다.

 

	vec = vector<int>(n + 1);
	dp = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));

먼저  배열이 저장될 벡터 vec와 메모라이즈 된 값이 저장될 벡터 dp를 만들어주었다.

여기서 dp[i][j]의 의미는 i번째 배열까지 탐색했을 때, j개의 구간으로 조합했을 때의 최댓값을 나타내며,

메모라이즈 여부를 확인하기 위해서 -1로 초기화하였다. 

int search(int n, int m) {
	if (m == 0)
		return 0;
	if (n <= 0)
		return -987654321;
	if (dp[n][m] != -1)
		return dp[n][m];

	dp[n][m] = search(n - 1, m);
	int partial_sum{}, temp;

	for (int i = n; i > 0; --i) {
		partial_sum += vec[i];
		temp = partial_sum + search(i - 2, m - 1);
		if (temp > dp[n][m])
			dp[n][m] = temp;
	}

	return dp[n][m];
}

위 코드가 dp를 이용하여 원하는 값을 찾는 함수로

	if (m == 0)
		return 0;
	if (n <= 0)
		return -987654321;
	if (dp[n][m] != -1)
		return dp[n][m];

함수 앞부분에서는 값이 존재하지 않거나, 값이 이미 저장되어 있어서 굳이 탐색을 안 해도 되는 경우를 처리해주었다.

	dp[n][m] = search(n - 1, m);
	int partial_sum{}, temp;

	for (int i = n; i > 0; --i) {
		partial_sum += vec[i];
		temp = partial_sum + search(i - 2, m - 1);
		if (temp > dp[n][m])
			dp[n][m] = temp;
	}

	return dp[n][m];

그리고 마지막 탐색 부분에서는 먼저 dp[n][m]을 dp [n-1][m]으로 만들어주었다.

이어서 배열의 n번째 구간부터 0번째 구간까지 역순으로 탐색을 진행하는데, 배열의 i번째에서 n번째 구간의 합과

dp [i-2][m-1]의 값의 합이 dp [n][m]보다 크면 계속 갱신을 진행해나가며 값을 찾고 마지막으로 원하는 값을 리턴해주었다.

 

 

전체 코드

 

C++

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> dp;
vector<int> vec;

int search(int n, int m) {
	if (m == 0)
		return 0;
	if (n <= 0)
		return -987654321;
	if (dp[n][m] != -1)
		return dp[n][m];

	dp[n][m] = search(n - 1, m);
	int partial_sum{}, temp;

	for (int i = n; i > 0; --i) {
		partial_sum += vec[i];
		temp = partial_sum + search(i - 2, m - 1);
		if (temp > dp[n][m])
			dp[n][m] = temp;
	}

	return dp[n][m];
}
int main(void)
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);

	int n, m;
	cin >> n >> m;

	vec = vector<int>(n + 1);
	dp = vector<vector<int>>(n + 1, vector<int>(m + 1, -1));

	for (int i = 1; i <= n; ++i)
		cin >> vec[i];

	cout << search(n, m);

	return 0;
}