백준 10844 < 쉬운 계단 수 > JavaScript

📍문제 링크

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

10844번: 쉬운 계단 수

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

- 수의 길이가 주어질 때, 계단 수의 총 가짓수를 구하라

- 계단 수 : 12345, 10101 처럼 각 자릿수가 1씩 증감하는 수

 

- 이차원 배열 memo가 있고

- row : N

- column : 맨 마지막 숫자 일때,

N=2 까지 아래와 같은 2차원 배열을 만들 수 있다

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

 

N = 2 일때,

- 마지막 숫자가 1인 경우는 memo[2][1] 이라고 할 수 있다 (편의상 0 row는 제외)

- 그리고 memo[2][1] 에서 앞 숫자는 0 또는 2 만 올 수 있다. (01, 21)

- 하지만 01 은 만들 수 없으므로 21만 가능해서 memo[2][1] =  memo[1][0] + memo[1][2] = 1이 된다

 

이를 정리하면

- memo[n][0] = memo[n-1][1]

- memo[n][1] = memo[n-1][0] + memo[n-1][2]

...

- memo[n][9] = memo[n-1][8] 의 규칙이 성립함을 알 수 있다.

 

📍의사 코드

- memo 이차원 배열을 만든다 (row : N개, column: 10개)

- 규칙에 따라 memo를 완성하는 반복문을 구성한다

- reduce를 통해 memo[n-1] 의 총합을 계산하고 마지막에는 10억으로 나눈 나머지를 출력한다 (BigInt 사용해야 함)

 

📍코드 (JavaScript)

const input = require("fs").readFileSync("/dev/stdin").toString().trim();
const N = +input;
const memo = Array.from({ length: N }, (_) =>
  Array.from({ length: 10 }, (_) => 0),
);

// 0 row 미리 준비
for (let i = 1; i < 10; i++) {
  memo[0][i] = 1;
}

for (let i = 1; i < N; i++) {
  memo[i][0] = BigInt(memo[i - 1][1]);
  for (let j = 1; j < 9; j++) {
    memo[i][j] = BigInt(memo[i - 1][j - 1]) + BigInt(memo[i - 1][j + 1]);
  }
  memo[i][9] = BigInt(memo[i - 1][8]);
}

console.log((BigInt(memo[N - 1].reduce((acc, cur) => BigInt(acc) + BigInt(cur), 0)) % 1000000000n).toString());

 

📍리뷰

- 규칙성을 찾을 때, DP를 이용한다면 미리 계산한 결과를 활용해나가는 것에 착안한다.