이 글은 백준 10844번 쉬운 계단 수를 풀이한다. 코드는 javascript로 작성하였다.

문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

예제 입력 1

1

예제 입력 2

2

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 출력 1

9

예제 출력 2

17

제한

• 시간: 1초
• 메모리: 256MB

풀이

길이가 N인 계단수가 총 몇 개 있는지 구하기 위해, 우선 길이가 1인 계단수 중 0~9로 끝나는 계단수가 각각 몇 개인지 저장한다(초기값 설정).
그 후 2부터 N까지 차례로 0부터 9까지 길이가 하나 작은 계단수 중 자신보다 1 작은 수와 1 큰 수로 끝나는 계단수의 개수 합을 저장한다. 이때 기존 계단수의 맨 오른쪽 숫자가 0이나 9라면 뒤에 각각 1과 8만 붙일 수 있기 때문에 이를 고려해야 한다. 그리고 정답을 10억으로 나눈 나머지를 출력하면 되기 때문에, 애초에 저장할 때부터 합을 10억으로 나누어 저장한다.
N까지 계단수의 개수를 다 구한 후 길이가 N인 계단수의 총 개수를 10억으로 나누어 출력하면 된다.

구현

코드

const input = [];

require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', function (line) {
    input.push(Number(line.trim()));
  })
  .on('close', function () {
    const N = Number(input[0]);
    const memo = [[0, 1, 1, 1, 1, 1, 1, 1, 1, 1]];
    let t = N - 1;
    while (t--) {
      memo.push([...Array(10)]);
    }
    for (let n = 1; n < N; n++) {
      for (let i = 0; i <= 9; i++) {
        memo[n][i] =
          ((memo[n - 1][i - 1] || 0) + (memo[n - 1][i + 1] || 0)) % 1000000000;
      }
    }
    const result = memo[N - 1].reduce((acc, curr) => {
      return (acc + curr) % 1000000000;
    }, 0);

    console.log(result);
  });