[JS] 1, 2, 3 더하기 - 백준 9095

문제

시간복잡도

O(n)

해결방법

i는 i-1을 만드는 방법 + 1, i-2를 만드는 방법 + 2, i-3을 만드는 방법 +3을 통해 만들 수 있다. (1+2와 2+1는 다르기 때문에 가능)

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

 

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./example.txt";
let input = fs.readFileSync(filePath).toString().split("\n");

let dp = [0, 1, 2, 4];
let max_num = Math.max(...input.slice(1));
console.log(max_num);
for (let i = 4; i <= max_num; i++) {
  dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}

for (let i = 1; i <= input[0]; i++) {
  console.log(dp[parseInt(input[i])]);
}