[백준][dp] 1965 상자넣기 NodeJs 구현

     

목차

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

문제

 

 

 

문제 구현 방향

dp로 푸는 문제로 현재 상자보다 작은 값인 상자의 누적값을 계산해주면 된다.

 

 

코드 구현

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

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


for (let i = 0; i < N; i++) {
  let cnt = 0;
  for (let j = 0; j < i; j++) {
    if (arr[i] > arr[j]) {
      cnt = Math.max(cnt, dp[j]);
    }
  }
  dp[i] = cnt + 1;
}
console.log(Math.max(...dp));