[백준10844_자바스크립트(javascript)] - 쉬운 계단 수

🔴 문제

쉬운 계단 수

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const n = Number(fs.readFileSync(path));
const dp = Array.from({ length: n }, () => Array(10).fill(0n));
const MOD = 1000000000n;

for (let i = 1; i <= 9; i++) {
  dp[0][i] = 1n;
}

for (let i = 1; i < n; i++) {
  for (let j = 0; j <= 9; j++) {
    if (j > 0) dp[i][j] += dp[i - 1][j - 1];
    if (j < 9) dp[i][j] += dp[i - 1][j + 1];
    dp[i][j] %= MOD;
  }
}

const answer = dp[n - 1].reduce((pre, cur) => BigInt(pre) + BigInt(cur), 0n);

console.log((answer % 1000000000n).toString());

🟢 풀이

⏰ 소요한 시간 : 30분 이상
이런 문제는 n=4까지 그림 그려보면 나오는데 답이 안나왔다.
정확히는 규칙은 알겠는데 어떻게 접근해야할 지 모르겠었다. 그래서 풀이봤다.
답이 안나올만함. 처음보는 풀이법 ㅋㅋ 2차원 dp는 처음봤다... ㅋㅋ;;
유튜브 풀이를 한 번 보고 내 방법대로 응용했다.

위의 사진처럼 2차원 배열로 만들어 n이 1일 때의 각 계단수의 개수를 채워 넣는다.
초기 상태는 위와 같을 것이다.
n 이 2일 경우는 아래와 같다.

사실 규칙은 쉬운데 2차원 배열을 떠올리기가 어려웠다.
표를 채우는 공식은 아래와 같다.

for (let i = 1; i < n; i++) {
  for (let j = 0; j <= 9; j++) {
    if (j > 0) dp[i][j] += dp[i - 1][j - 1];
    if (j < 9) dp[i][j] += dp[i - 1][j + 1];
    dp[i][j] %= MOD;
  }
}

큰 수가 될 수 있으므로 중간중간 모듈러 연산도 포함해 주면 된다.

🔵 Ref

https://www.youtube.com/watch?v=SPVOKqMDerQ