11057 오르막 수 (자바스크립트)

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

===

문제 분석

2236 라는 숫자 이후에 만들 수 있는 다섯자리 오르막 수는 

22367 22368 22369 이다

모든 수의 끝자리에 그 이상의 수를 붙이면 다음 자릿 수를 갖는 오르막 수를 구할 수 있다는 뜻이다.

이를 위해 각 자릿수를 row로 갖고 끝자리에 올 수 있는 0~9사이의 수를 col로 갖는 2차원 dp 를 선언한다.

숫자는 0부터 시작할 수 있기 때문에 자릿수가 한자리일때 dp는 아래와 같이 초기화한다.

const dp = Array.from({ length: n + 1 }, () =>
    Array.from({ length: 10 }).fill(0)
);
for (let i = 0; i < 10; i++) {
    dp[1][i] = 1;
}

이후에는 현재 탐색 중인 i의 각 끝자리수는 그 끝자리 이하의 이전 수들을 탐색하면 되므로 아래와 같이 반복문을 실행한다.

for (let i = 2; i < n + 1; i++) {
    for (let j = 0; j < 10; j++) {
        for (let prev = j; prev >= 0; prev--) {
            dp[i][j] = (dp[i][j] + dp[i - 1][prev]) % INF;
        }
    }
}

정답 코드

const input = require('fs')
    .readFileSync(process.platform === 'linux' ? '/dev/stdin' : './input.txt')
    .toString()
    .trim()
    .split('\n');

const n = +input[0];
const INF = 10_007;
const dp = Array.from({ length: n + 1 }, () =>
    Array.from({ length: 10 }).fill(0)
);
for (let i = 0; i < 10; i++) {
    dp[1][i] = 1;
}
for (let i = 2; i < n + 1; i++) {
    for (let j = 0; j < 10; j++) {
        for (let prev = j; prev >= 0; prev--) {
            dp[i][j] = (dp[i][j] + dp[i - 1][prev]) % INF;
        }
    }
}

console.log(dp[n].reduce((acc, cur) => (acc + cur) % INF, 0));