[JavaScript] 백준 10844 쉬운 계단 수 (JS)

쉬운 계단 수

📚 문제 설명

45656 와 같이 모든 숫자가 1의 차이로 있는 숫자를 계단 수라고 한다.
N의 길이의 계단 수는 모두 몇개인지 구하여라.

단, 계단수의 첫번째 숫자는 0이 될 수 없다.

👨🏻‍💻 풀이 과정

이 문제에서 다음에 올 숫자를 정하는 것은 이전에 어떤 숫자에 따라 정해진다.

예를 들어, 만약 두번째 자리에 숫자 0이 들어온다면 (ex : #0)
첫번째 자리는 무조건 1이어야 한다. (ex : 10)

따라서 dp[i][j] 라는 2차원 배열을 만들어서
i 번째 자리에 숫자 j가 올 경우의 수를 저장한다.

그리고 dp[i][j] 는 dp[i - 1][j - 1] + dp[i - 1][j + 1] 일 것이다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    let N = parseInt(input.shift());

    let dp = new Array(N);
    for (let i = 0; i < dp.length; i++) {
        dp[i] = new Array(10).fill(1);
    }
    dp[0][0] = 0;
    for (let i = 1; i < N; i++) {
        for (let j = 0; j < 10; j++) {
            if (j === 0) {
                dp[i][j] = dp[i - 1][1] % 1000000000;
            }else if (j === 9) {
                dp[i][j] = dp[i - 1][8] % 1000000000;
            } else {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
            }
        }
    }
    console.log(dp[N - 1].reduce((acc, cur) => {
        return (acc + cur) % 1000000000
    }, 0));

원래는 마지막 reduce() 에서만 나머지 계산을 진행했는데 그렇게 풀면 틀렸다고 나오게 된다.
따라서 dp[i][j] 배열에 저장할 때마다 계산을 진행했다.

🧐 후기

최근 DP 관련 문제를 풀고 있는데 이제 조금씩 감이 잡히는 것 같다.
DP 관련 문제는 다른 문제보다 손으로 적으면서 많이 풀게 되는 문제인듯하다.