[node.js,백준]11057 - 오르막수

목차

 문제

링크

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

 

문제

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

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

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

 

입력

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

 

출력

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

 

주저리

수는 0부터가능하기때문에 0~9까지 첫번째는 각 경우의 수는 1이다.

이후로는 자기랑 같은수부터 높은수를 더해야하는데

순서는 정렬이되어있는 상태이므로

slice(j,10)으로 자기부터 높은수를 자른후 더해준게 총자리의 경우의 수이다.

마지막은 경우의수 0~9까지를 다 더해서 제출하면된다.

 

풀이

 초기화과정

• - 길이가 1인 모든 오르막 수는 각각의 숫자 자체로 구성됩니다. 따라서 길이가 1인 오르막 수의 개수는 0부터 9까지 각각 1개씩, 총 10개입니다.

 동적 계획법의 적용

• - `dp[i][j]`는 길이가 `i+1`이며 마지막 숫자가 `j`인 오르막 수의 개수를 나타냅니다.
• - 각 `dp[i][j]` 값은 `j` 이상의 숫자로 끝나는 길이가 `i`인 오르막 수의 개수의 합으로 계산됩니다.

 결과 계산

• - 최종적으로 길이 `N`의 모든 오르막 수의 개수는 `dp[N-1][0]`부터 `dp[N-1][9]`까지의 값들을 모두 더하여 계산합니다.

 코드

// 오르막수

var fs = require('fs');
// var input = fs.readFileSync('/dev/stdin').toString();
let input = `3`
let real = input.trim().split("\n");
let arrs = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]];
let mod = 10007
function solution(real) {
    let [T, ...rest] = real;

    for (let i = 1; i < Number(T); i++) {
        arrs.push([])
        for (let j = 0; j < 10; j++) {

            arrs[i][j] = arrs[i - 1].slice(j, 10).reduce((acc, cv) => (acc % mod) + (cv % mod), 0);
        }
    }
    // console.log(arrs)
    console.log(arrs[T - 1].reduce((acc, cv) => acc + cv, 0) % mod)

}
solution(real);