쉬운 계단 수

문제

언어

  • JavaScript

문제 풀이 step 1

  • dp[n] = 길이가 n인 계단 수의 총 개수
  • DP의 특징인 작은 문제의 해답으로부터 큰 문제의 해답을 찾는다를 이용합니다.
  • 계단 수는 0 ~ 9의 수로 이루어져 있습니다.
  • 그렇다면 계단 수의 맨 뒤에는 0 ~ 9 즉, 10개의 수로만 구성됩니다. 경우의 수는 10가지입니다. (계단 수는 인접한 모든 자리수의 차이가 1입니다.)
    • 길이가 n이고, 뒤에 0이 오는 계단 수 : dp[n][0] = dp[n-1][1]
    • 길이가 n이고, 뒤에 1이 오는 계단 수 : dp[n][1] = dp[n-1][0] + dp[n-1][2]
    • …
    • 길이가 n이고, 뒤에 9가 오는 계단 수 : dp[n][9] = dp[n-1][8]
  • 마지막 단계의 바로 한 단계의 전을 고려해서 점화식을 뽑아냅니다.

소스 코드

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

const solution = (input) => {
	const N = parseInt(input[0]);
	const MOD = 1000000000;
	const dp = Array.from({length: N + 1}, () => []);

	// BASE
	dp[1][0] = 0;
	for (let i = 1; i < 10; i++) {
		dp[1][i] = 1;
	}

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

	let sum = 0;
	for (let i = 0; i < 10; i++) {
		sum += dp[N][i];
		sum %= MOD;
	}

	return sum;
};

console.log(solution(input));