[백준] 10844 쉬운 계단 수 - javascript

📌 문제

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

📌 풀이

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

const n = +input.shift();
const dp = Array.from({ length: n + 1 }, () =>
  Array.from({ length: n + 1 }, () => 0)
);
const mod = 1000000000;

for (let i = 1; i < 10; i++) {
  dp[1][i] = 1;
}

for (let i = 2; i <= n; i++) {
  for (let j = 0; j < 10; j++) {
    if (j === 0) dp[i][0] = dp[i - 1][1];
    else if (j === 9) dp[i][9] = dp[i - 1][8];
    else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];

    dp[i][j] %= mod;
  }
}

let ans = 0;
for (let i = 0; i < 10; i++) {
  ans += dp[n][i];
  ans %= mod;
}

console.log(ans);

✔ 알고리즘 : DP

✔ 1차원 배열의 DP로 풀다가 계속 틀렸습니다를 받아서 2차원 DP로 풀어보게 되었다.

✔ dp[i][j] 👉 길이가 i이고 끝자리가 j로 끝나는 계단수의 갯수

✔ 길이가 1일 때 dp[1][1~9]를 1로 초기화 시켜놓고 dp탐색을 시작

✔ i가 2이상일 때

• dp[i][0]
  길이가 하나 적은 dp[i-1]의 1번째 index 즉, dp[i-1][1]밖에 올 수 없다.
• dp[i][9]
  길이가 하나 적은 dp[i-1]의 8번째 index 즉, dp[i-1][8]밖에 올 수 없다.
• dp[i][j] (1 <= j <= 8)
  길이가 하나 적은 dp[i-1]의 j-1번째, j+1번째 index가 올 수 있다.

✔ 난이도 : 백준 기준 실버 1