백준 11052 카드구매하기 (NodeJs)

주의사항
Top down방식 일때 memoiazation 해주지 않으면 시간초과 발생

Top down

let input = [];
let d = [];
var require = require("readline")
  	.createInterface(process.stdin, process.stdout)
 	.on("line", function(line) {
    input.push(line.trim());
  	})
  	.on("close", function() {
      	for (let i = 0; i <= input[0]; i++) {
			d.push(0);

}
let k= input[1].split(" ")
sellingCard(input[0],k);
console.log(d[input[0]]);
})

const sellingCard = (n,k) => {

if (d[n] > 0) {
return d[n];
}
for (let i = 1; i <= n; i++) {
d[n] = Math.max(d[n], sellingCard(n - i , k) + Number(k[i - 1]));
}
return d[n];
};

Bottom up

let input = [];
let d = [];
var require = require("readline")
  	.createInterface(process.stdin, process.stdout)
  	.on("line", function(line) {
    	input.push(line.trim());
  		})
  	.on("close", function() {
  		let cardArr = input[1].split(" ");

for (let i = 0; i <= input[0]; i++) {
d.push(0);
}
for (let i = 1; i <= input[0]; i++) {
for (let j = 1; j <= i; j++) {
d[i] = Math.max(d[i], d[i - j] + Number(cardArr[j - 1]));
}
}
console.log(d[input[0]]);
})