[백준][DP] 2240 자두나무 NodeJs 구현

     

목차

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

문제

 

 

코드 구현 방향

상태가 총 3개이므로 그에 맞추어 3차원 배열로 메모이제이션해 풀어야 한다.

이때 dp는 그 전 상태의 최댓값을 받아서 누적해 주는 형식으로 가야 한다.

 

 

코드 구현 시 주의점

처음에 1번 나무에서 시작하지만 움직이고 시작할 수 있기 때문에 처음 시작점을 두개로 하고 max를 구해주어야 한다.

 

 

코드 구현

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

//sec cnt num

let [T, W] = input[0].trim().split(" ").map(Number);
let dp = Array.from({ length: T + 1 }, () =>
  Array.from({ length: W + 1 }, () => Array(2).fill(0))
);

let idx = 1;
let tree = [];
while (idx < input.length) {
  tree.push(+input[idx] - 1);
  idx++;
}

searching(1, W, 0);

function searching(sec, cnt, num) {
  if (cnt < 0) return -1;
  if (sec === T) return 0;
  if (dp[sec][cnt][num]) return dp[sec][cnt][num];
  return (dp[sec][cnt][num] =
    Math.max(
      searching(sec + 1, cnt - 1, num ^ 1),
      searching(sec + 1, cnt, num)
    ) +
    (tree[sec] === num));
}
console.log(Math.max(searching(0, W - 1, 1), searching(0, W, 0)));