[백준 10844] 다이나믹 프로그래밍 - 쉬운 계단 수

✨ 문제 ✨

✨ 정답 ✨

// const fs = require("fs");
// const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
// let input = fs.readFileSync(filePath).toString().trim();

// const fs = require('fs'); 
// let input = fs.readFileSync('/dev/stdin').toString().trim();

// const N=+input

// let dp=[];
// dp[0]=9;

// const answer = (n)=>{
//     for (let i=1;i<n;i++){
//         dp[i]=dp[i-1]*2-i;
//     }
// }
// answer(N)
// console.log(dp[N-1])





// https://nyang-in.tistory.com/273
let fs = require("fs");
const number = Number(fs.readFileSync("예제.txt").toString());

// dp[n][i] = n자리 수이면서 i로 끝나는 수
const dp = Array.from(new Array(number + 1), () => new Array(10));

dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
dp[2] = [1, 1, 2, 2, 2, 2, 2, 2, 2, 1];

for (let n = 3; n <= number; n++) {
  for (let i = 0; i < 10; i++) {
    if (i === 0) {
      dp[n][i] = dp[n - 1][i + 1] % 1000000000;
    } else if (i >= 1 && i <= 8) {
      dp[n][i] = (dp[n - 1][i - 1] + dp[n - 1][i + 1]) % 1000000000;
    } else {
      dp[n][i] = dp[n - 1][i - 1] % 1000000000;
    }
  }
}
let sum = 0;
for (let j = 0; j < 10; j++) {
  sum += dp[number][j];
}

console.log(sum % 1000000000);

💡💡 기억해야 할 점 💡💡

1. if문으로 조건을 나누는 것을 두려워하지 말자