boj 2228 구간 나누기

www.acmicpc.net/problem/2228

2228번: 구간 나누기

이 문제는 조건을 잘 확인해야 합니다.

1. 각 구간은 한 개 이상의 연속된 수들로 이루어진다.

2. 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.

3. 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다

6 2
-1
3
1
2
4
-1

위 예제에서의 답은 {3}과 {2, 4}를 선택하여 9입니다.

 

dp[idx][cnt] = 구간의 시작인덱스가 idx이고 cnt번째 구간일 때의 최댓값>

idx가 구간의 시작점이고, 구간의 끝은 반복문을 통해 구하였습니다.

 

구간의 끝을 구하기 전에 idx번째 수를 선택하지 않을 수도 있기때문에 먼저 구해주었습니다.

idx ~ i의 구간을 골랐으면 다음 구간은 이 구간과 인접해있으면 안되기때문에 i+2를 넘겨주었습니다.

 

정확히 M개를 골랐으면 합의 최댓값을 갱신, 남은 배열에서 M개의 구간을 못 고르는 경우 MIN값을 리턴하였습니다.

 

 

#include <iostream>
#include <algorithm>
#define INF 1000000000
using namespace std;
 
int list[101], sum[101], dp[101][51];
int N, M;
 
int func(int idx, int cnt) {
    if (cnt == M) return 0;
    if ((N - idx + 2) / 2 < M - cnt) return -INF;
 
    int &ret = dp[idx][cnt];
    if (ret != -INF) return ret;
    ret = func(idx + 1, cnt);
 
    for (int i = idx; i <= N; i++) {
        ret = max(ret, func(i + 2, cnt + 1) + sum[i] - sum[idx - 1]);
    }
 
    return ret;
}
 
void init() {
    for (int i = 0; i <= N; i++) {
        for (int j = 0; j <= M; j++) {
            dp[i][j] = -INF;
        }
    }
}
 
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> list[i];
        sum[i] = sum[i - 1] + list[i];
    }
    init();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    cout << func(1, 0) << '\n';
 
    return 0;
}