[백준 11057번 오르막 수 - node.js] [알고리즘 기초 1/2]

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

11057번: 오르막 수

 

문제

 

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

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

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

 

입력

 

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

 

출력

 

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

 

예제 입출력

 

입력	출력
1	10
2	55
3	220

 

풀이[node.js]

 

 

728x90

 

이번 문제는 왠지 설명하기 조금 어려웠다.

우선 1자리수 중에서 0으로 끝나는 수는 1개, 1로 끝나는 수는 1개......9로 끝나는 경우의 수도 1개이다.

 

이를 이용해서, 2자리수를 구해보자.

0으로 끝나는 두자리수의 앞엔 0과 같거나 작은 수만 올 수 있다.

그래서 0으로 끝나는 수 1이 된다.

1로 끝나는 두자리수의 앞엔 1과 같거나 작은 수만 올 수 있다.

1자리수에서 0과 1로 끝나는 수의 경우의 수는 각각 1, 1이므로 1로 끝나는 두자리수의 경우의 수는 1+1 = 2가된다.

마찬가지로 9로 끝나는 2자리수에선 0~9로 끝나는 모든 1자리수가 올 수 있다.

그러므로 1+1+1+1+1+1+1+1+1+1 = 10이 된다.

 

마찬가지로, 0으로 끝나는 3자리수는 000으로 1개 뿐이다.

1로 끝나는 3자리수는 0과 1로 끝나는 2자리수의 경우의 수를 더한 값이므로, 1+2 = 3이다.

2로 끝나는 3자리수는 0, 1, 2로 끝나는 2자리수의 경우의 수를 더한 값이므로, 1+2+3 = 6이다.

마지막으로 9로 끝나는 3자리수는 0~9로 끝나는 2자리수의 경우의 수를 모두 더한 값이므로, 10+9+8+7+6+5+4+3+2+1 = 55가 된다.

  

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString();
inputs = Number(inputs);
var dp = [[], new Array(10).fill(1)];
for(var i=2; i<=inputs; i++){
    dp[i] = [];
    dp[i][0] = dp[i-1][0] % 10007;
    for(var j=1; j<10; j++){
    	dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 10007;    
    }
}
console.log(dp[inputs].reduce((a,v)=> a+v, 0) % 10007);