2228번: 구간 나누기
N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야
www.acmicpc.net
이 문제는 조건을 잘 확인해야 합니다.
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값을 리턴하였습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#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;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 1937 욕심쟁이 판다 (0) | 2021.03.28 |
|---|---|
| boj 2201 이친수 찾기 (2) | 2021.03.24 |
| boj 1695 팰린드롬 만들기 (0) | 2021.03.20 |
| boj 9177 단어 섞기 (0) | 2021.03.19 |
| boj 10942 팰린드롬? (0) | 2021.03.12 |