🎲 백준 15988번 1, 2, 3 더하기 3

백준 15988번

const fs = require('fs'); 
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const T = +input.shift();
const dp = new Array(Math.max(...input));
dp[0] = 1;
dp[1] = 2;
dp[2] = 4;

for (let i = 3; i < dp.length; i++) {
  dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000009;
}
for (let t = 0; t < T; t++) {
  console.log(dp[input[t] - 1]);
}