백준 10844번 쉬운 계단 수 - node.js

해당 포스팅은 백준 10844번 쉬운 계단 수 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.

---

문제

문제 설명

• 계단수: 인접한 모든 자리의 차이가 1인 수 (EX. 45656)
• N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자.
• 0으로 시작하는 수는 계단수가 아니다.

입력

[첫째 줄] : N (1 ≤ N ≤ 100)

출력

[첫째 줄]: 정답 % 1,000,000,000

---

풀이

로직 설명

N = 2일 때 가능한 계단수를 생각해보자.
10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98 가 있다.

해당 숫자들을 보면 십의자리 숫자들은 일의자리 숫자가 무엇이 오는지에 따라 올 수 있는 단어들이 정해진다.

일의 자리 수가 0일 때 1차이가 날 수 있는 자연수는 오직 1뿐이다.
반면 2부터 8까지 자연수는 자기 자신의 +1, -1인 숫자가 올 수 있다. 예시로 일의 자리 수가 8일 때 가능한 계단수는 78, 98이 있다.
일의 자리 수가 9일 때 1차이가 날 수 있는 자연수는 오로지 8뿐이다.

이처럼 이전의 숫자들이 어떤 값인지에 따라 올 수 있는 답이 정해져있다. 즉 이전 자리수(부분합)을 먼저 구해야 하는 문제이므로 DP로 풀이하면 된다.

---

예제 설명

N = 3일 때를 예시로 설명하겠다.

위의 표들을 보면 N이 3일 때 가능한 조합은 총 32개가 있다.

[N=1]일 때 1~9까지 각 자연수가 가능하다. 0은 자연수가 아니므로 불가능하다.
[N=2]일 때

• j = 0일 때 자기 자신 +1인 10('1'+'0')만 가능하다.
• j = 1일 때 자기 자신 +1인 21('2'+'1')만 가능하다.
• j가 2~8사이의 자연수일 때는 자기 자신 +1, -1이 가능하다.
• j가 9일 때는 자기 자신 -1인 89('8'+'9')만 가능하다.

[N=3]일 때

• j = 0일 때
  dp[3][0]는 dp[2][1](210) + '0'이다.
• j = 1~8일 때
  j가 1~8일 때 조합들을 살펴보면 dp[3][j] = dp[2][j-1] + dp[2][j+1]임을 확인할 수 있다.
• j = 9일 때
  dp[3][9]는 dp[2][8](78, 98) + '9'임을 확인할 수 있다.

j=0, 9일 때 각각 dp[i][j] = dp[i-1][j-1], dp[i][j] = dp[i-1][j+1]이다. 반면 j=1~8일 때는 dp[3][j] = dp[2][j-1] + dp[2][j+1]이다. 그 이유는 인덱스 -1과 10인 원소가 없기 때문이다.

따라서 해당 로직을 점화식으로 표현하면 아래와 같다.

---

점화식

JS의 비교연산자를 이용해 위의 로직을 아래의 점화식으로 표현할 수 있다.

점화식
DP[i][j] = DP[i-1][j-1] || 0 + DP[i-1][j+1] || 0
(0 ≤ j ≤ 9)

---

전체 코드

const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);

const DP = new Array(N)

for (let i=0; i<N; i++) {
    DP[i] = new Array(10).fill(0)
}

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

for (let i=1; i<N; i++) {
    for (let j=0; j<=9; j++) {
        DP[i][j] = (DP[i-1][j-1] || 0) + (DP[i-1][j+1] || 0) % 1000000000;
    }
}

const result = DP[N - 1].reduce((acc, curr) => {
  return (acc + curr) % 1000000000;
}, 0);

console.log(result);