BOJ 2228 - 구간 나누기

문제

N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.

1. 각 구간은 한 개 이상의 연속된 수들로 이루어진다.
2. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.
3. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.

N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 배열을 이루는 수들이 차례로 주어진다. 배열을 이루는 수들은 -32768 이상 32767 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

접근

문제 설명이 이상해서 처음에 해석을 잘못해 다른 방향으로 풀었다.
인접하지 않은 M개의 구간을 선택해서 다 더하는 문제이다.

3차원 테이블 dp[N][M][K]를 놓았다.
이는 i번째 index까지 j개의 구간이 있을때,
k = 0 일 때, i번째 index를 사용하지 않은 경우.
k = 1 일 때, i번째 index를 사용한 경우이다.
인접하지 않게 구간을 만들기 위해 2크기의 K를 놓았다.

풀이

dp[i][j][0]은 dp[i - 1][j][0 or 1] 중 큰 값을 갖는다.
dp[i][j][1]은 dp[i - 2][j - 1][0 or 1] + arr[i], dp[i - 1][j][1] 중 큰 값을 갖는다.
처음 초기화만 잘 해주면 바로 답이 풀린다.
INT_MIN으로 설정했다가 언더플로우가 나서, -1e6으로 바꿔주었다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };

int N, M, arr[101], dp[101][51][2];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	MS(dp, 0);
	CIN2(N, M);
	FUP(j, 0, M) dp[0][j][0] = dp[0][j][1] = -1e6;
	dp[0][0][0] = 0;
	FUP(i, 1, N)
	{
		CIN(arr[i]);
		dp[i][0][0] = dp[i][0][1] = 0;
		FUP(j, 1, M) dp[i][j][0] = dp[i][j][1] = -1e6;
	}
	dp[1][1][1] = arr[1];
	FUP(i, 2, N)
	{
		FUP(j, 1, M)
		{
			dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1]);
			dp[i][j][1] = max({ dp[i - 2][j - 1][0], dp[i - 2][j - 1][1], dp[i - 1][j][1] }) + arr[i];
		}
	}

	COUT(max(dp[N][M][0], dp[N][M][1]));

	return 0;
}