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

문제

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

• N이 주어질 때, N자리 숫자 중 계단 수의 총 개수를 알아내는 문제

풀이

• 점화식을 수도코드로 적어보자면 아래와 같다. (초기화, 나머지 로직 생략한 핵심)

for (let i = 2; i <= N; i++) {
  for (let j = 0; j <= 9; j++) {
    if (j >= 1) dp[i][j] += dp[i - 1][j - 1];
    if (j < 9) dp[i][j] += dp[i - 1][j + 1];
  }
}

생각

• 점화식을 세울 때 명확한 근거를 통해 세워야 한다.
• 처음 접근했을 메모이제이션할 배열을 일차원으로 정의하고 접근했다. N자리일 경우 계단 수의 개수가 N+1자리의 경우 계단 수의 개수와 관계가 있다고 접근했으나, 이렇게 가정하고 풀면 이전에 어떤 숫자로 끝났는지에 의존해 다음 숫자가 결정되는지를 정의할 수가 없었다. 그 상태로 몇일간 풀지 못하고 있었는데, 어제 풀이했던 LIS 문제를 통해 동적 프로그래밍 문제에 대한 감을 다시 찾고 나니 점화식이 보였다!
• 이차원 배열로 이전에 끝나는 수의 개수를 저장해두면, 그 수와 1 차이나는 계단수의 개수를 정의할 수 있다. 결과적으로 쉬운 계단 수 문제이지만 전혀 쉽지 않았다. 그러나 꼭 풀어봐야 할 문제였던 것 같다!

전체 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = input();
  const dp = [];
  dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];
  for (let i = 2; i <= N; i++) {
    dp[i] = [];
    for (let j = 0; j <= 9; j++) {
      dp[i][j] = 0;
      if (j >= 1) dp[i][j] += dp[i - 1][j - 1];
      if (j < 9) dp[i][j] += dp[i - 1][j + 1];
      dp[i][j] %= 1000000000;
    }
  }
  console.log(dp[N].reduce((sum, elem) => sum + elem, 0) % 1000000000);
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});