문제
N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.
- 각 구간은 한 개 이상의 연속된 수들로 이루어진다.
- 서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.
- 정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.
N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 배열을 이루는 수들이 차례로 주어진다. 배열을 이루는 수들은 -32768 이상 32767 이하의 정수이다.
출력
첫째 줄에 구간에 속한 수들의 총 합의 최댓값을 출력한다.
풀이
1번째 원소부터 포함할 때와 포함하지 않을 때의 j개의 구간합을 배열에 저장해가며 subproblem의 최적해를 찾아 DP로 풀이하였다.
incl[i][j] : i번째 원소를 포함한 j개의 구간합의 최댓값
not_incl[i][j] : i번째 원소를 포함하지 않는 j개의 구간합의 최댓값
답은 n번째 원소를 포함한 m개 구간합의 최댓값과 n번째 원소를 포함하지 않는 m개 구간합의 최댓값 중 큰 값이다.
n번째 원소를 포함한 m개 구간합의 최댓값 즉, incl[n][m]은 incl[i-1][j], not_incl[i-1][j-1] 중 큰 값이다.
n번째 원소를 포함하지 않는 m개 구간합의 최댓값 즉, not_incl[n][m]은 incl[i-1][j], not_incl[i-1][j] 중 큰 값이다.
코드
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");
const [n, m] = input.shift().split(" ").map(Number);
let arr = Array.from({ length : n }, () => +input.shift());
arr.unshift(0);
let incl = Array.from({ length : n+1 }, () => [0].concat(new Array(m).fill(-1e9)));
let not_incl = Array.from({ length : n+1 }, () => [0].concat(new Array(m).fill(-1e9)));
for (let i=1; i<n+1; i++) {
for (let j=1; j<Math.min(m, Math.ceil(i/2))+1; j++) {
not_incl[i][j] = Math.max(incl[i-1][j], not_incl[i-1][j]);
incl[i][j] = Math.max(incl[i-1][j], not_incl[i-1][j-1]) + arr[i];
}
}
console.log(Math.max(incl[n][m], not_incl[n][m]));