Node.js) 백준 15988번: 1, 2, 3 더하기 3

 

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

15988번: 1, 2, 3 더하기 3

const fs = require('fs');
const [T,...n] = fs.readFileSync("./dev/stdin").toString().trim().split("\n").map(Number);
const answer = [];
const div = 1000000009;

const dp = new Array(1000001).fill(0);
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;

for(let i = 4; i< 1000001; i++){
  dp[i] = (dp[i-3]+dp[i-2]+dp[i-1])%div;
}

n.forEach(v=>{
  answer.push(dp[v])
})

console.log(answer.join('\n'));