[백준][dp] 11052 카드 구매하기 NodeJs구현

목차

https://www.acmicpc.net/problem/11052

문제

 

문제 구현 방향

카드팩을 순서대로 순회하면서 그 전 카드팩의 최대의 조합을 비교하며 최댓값을 갱신해 주면된다.

 

 

 

코드 구현

const input = require("fs")
  .readFileSync("./dev/stdin", "utf-8")
  .trim()
  .split("\n");

let N = Number(input[0]);
let arr = input[1].trim().split(" ").map(Number);

let dp = new Array(1002).fill(0);

dp[1] = arr[0];

for (let i = 2; i <= N; i++) {
  let m = 0;
  for (let j = 1; j <= i; j++) {
    let a = j;
    let b = i - j;
    let sum = dp[a] + dp[b];
    m = Math.max(sum, m);
    if (a === b) break;
  }
  dp[i] = Math.max(m, arr[i - 1]);
}

console.log(dp[N]);