[백준 10844] 쉬운 계단 수 (node.js)

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

10844번: 쉬운 계단 수

---

풀이

- 길이가 N인 계단 수를 구하는 문제 (45656 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라 부름)

- '이때 0으로 시작하는 수는 계단수가 아니다' 는 조건이 있음

 

점화식

- 2차원 DP배열에서 i, j 에 의미 부여 후 점화식 세워 문제 풀이하는 방법을 따라함

- 직접 했을 때는 식을 못 찾고, 설명을 찾아보고 다시 그렸을 때야 이해가 되었음

DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]
- 이때 DP[i][j] 에서 i는 자릿수(길이), j는 끝 숫자를 의미
- DP[2][0], 두 자리수에 끝이 0인 수는 X0 로 표기

 

예시

 

i = 0 ~ 3(자리 수 길이), j = 0 ~ 9 (끝나는 수)

 

DP[2][2] 의 경우 두 자리 수에 끝이 2 (X2)인 경우를 찾을 경우 {12, 32} 와 같다. (이는 DP[1][1] 과 DP[1][3] 의 경우의 수를 더한 것과 같다.)

예시.
DP[3][1] = DP[2][0] + DP[2][2]

DP[3][1] => xx1

자리수가 2이고 끝자리가 0인 경우(x0)와 2인 경우(x2)를 생각해보자. 그리고 끝에 1을 더하면 계단수를 만족할 것이다.
DP[2][0] => {10} => 101
DP[2][2] => {12, 32} => 121, 321

고로 점화식과 같이 경우의 수를 더하여 원하는 값을 구할 수 있다 (이때 예외 처리 필요)

 

이를 식으로 나타내면 위의 점화식과 동일하게 구해진다.

DP[2][2] = DP[1][1] + DP[1][3]

DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1] 

 

이때 주의할 숫자가 0, 9 이다.

1) DP[2][0] (두 자리수 이고 끝자리가 0 인 경우) 과 같이 끝자리가 0인 경우 앞에 1(DP[1][1])만 가능  => {10}

DP[i][0] = DP[i - 1][j + 1];

2) DP[2][9] (두 자리수 이고 끝자리가 9 인 경우) 과 같이 끝자리가 9인 경우 앞에 8(DP[1][8])만 가능 => {89}

DP[i][9] = DP[i - 1][j - 1]

 

그외의 경우 점화식을 통해 풀이 하면 된다.

DP[2][3] = DP[1][2] + DP[1][4]  => DP[i][j] = DP[i - 1][j - 1] + DP[i - 1][j + 1]

 

위 식을 읽어보자면 두자리 수이고 끝이 3이되는 경우의 수는 

한 자리 수이고 끝이 2가 되는 경우의 수와 한 자리 수이고 끝이 4가 되는 경우의 수의 합과 같다.

(어차피 끝에 3만 붙이면 되니깐, 계단 수 의미를 만족하려면 위의 두 경우만 고려하면 됨)

 

//SUCCESS
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');

const n = Number(input[0]);
const dp = Array.from({length : n + 1}, () => new Array(10).fill(0));
const mod = Number(1e9);

dp[1][0] = 0; // 0으로 시작하는 수는 계단 수가 아님
for(let i = 1; i < 10; i++) {
    dp[1][i] = 1;
}

for(let i = 2; i <= n; i++) {
    for(let j = 0; j <= 9; j++) {
        dp[i][j] = 0;
        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;
    }
}

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

console.log(result);