[백준] 10844_쉬운 계단 수 (Javascript)

문제

BOJ10844_쉬운 계단 수

코드 ("틀렸습니다")

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./LJH/input.txt";
let n = Number(fs.readFileSync(filePath).toString());
let dp = {
    1: 9
};
for (let i = 2; i <= n; i++) {
    dp[i] = i % 2 === 0 ? (dp[i - 1] * 2 - 1) % 10 ** 9 : (dp[i - 1] * 2 - 2) % 10 ** 9;
}
console.log(dp[n]);

처음에는 1차원 dp테이블을 이용해서 풀어보려다가 틀렸다.
그래서 다른 사람들의 코드를 보고나서야 풀 수 있었다.
이 문제는 2차원 dp테이블을 이용하면 쉽게 풀수 있는 문제였다.

접근법

계단 수 라는 것은 어떤 수 x 가 있을 때 다음에 오는 수가 x+1 혹은 x-1 인 수를 말한다.

n=1일 경우 만들 수 있는 수는

1,2,3,4,5,6,7,8,9

총 9개다 (첫 번째 자리에는 0이 올 수 없음)

n=1이 아닐 경우, 어떤 수 i가 있을 때 계단 수를 만들려면 i+1에는 다음과 같은 수가 와야한다.

i	i+1
0	1
1	0,2
2	1,3
3	2,4
4	3,5
5	4,6
6	5,7
7	6,8
8	7,9
9	8

이를 이용하여 아래와 같이 각각 만들 수 있는 계단 수의 개수를 저장한 dp테이블을 만들 수 있다.

n=1 [0,1,1,1,1,1,1,1,1,1]
n=2 [1,1,2,2,2,2,2,2,2,1]
n=3 [1,3,3,4,4,4,4,4,3,2]
n=4 [3,4,7,7,8,8,8,7,6,3]

이를 바탕으로 아래의 점화식을 만들 수있다.

dp[1] = [0,1,1,1,1,1,1,1,1,1] 일때
dp[i][j] = 0 이라면, dp[i][j] = dp[i-1][j+1]
dp[i][j] = 9 라면, dp[i][j] = dp[i-1][j-1]
그 외의 경우, dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

따라서 아래와 같은 코드를 만들 수 있다.

코드 ("맞았습니다!!")

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./LJH/input.txt";
let n = Number(fs.readFileSync(filePath).toString());
let dp = {
    1: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1],
};
const mod = 10 ** 9;
for (let i = 2; i <= n; i++) {
    dp[i] = Array(10).fill(0);
    for (let j = 0; j <= 9; j++) {
        if (j === 0) dp[i][j] = dp[i - 1][j + 1];
        else if (j === 9) dp[i][j] = dp[i - 1][j - 1];
        else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
        dp[i][j] %= mod;
    }
}

let result = dp[n].reduce((acc, cur) => (acc + cur) % mod);
console.log(result);