[백준 10844번 쉬운 계단 수 - node.js] [알고리즘 기초 1/2]

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

10844번: 쉬운 계단 수

 

문제

 

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

입력

 

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

 

예제 입출력

 

입력	출력
1	9
2	17

 

풀이[node.js]

 

 

728x90

이번 문제는 dp의 기준이 0부터 9까지 각 숫자별로 해당 자리에 올 수 있는 가짓 수를 구하는 것입니다.

먼저, 1자리 수일 때는, 0은 올 수 없기에 0이고, 1~9는 한자리수에 올 수 있으므로 각각 1을 넣어 주었습니다.

여기서, 앞뒤로 1씩 크고 작은 값을 그 다음에 넣을 수 있으므로, 0은 가짓수가 없어서 줄 값이 없고, 1은 1뒤에 0또는 2가 올 수 있으므로, 0과 2자리에 1씩 추가해주고, 2 다음자리에는 1, 3이 올 수 있으므로, 1, 3값을 올려줍니다.

다음으로 3자리수 일 때는 2번째 자릿수에서 0인 경우가 1개 있었으니, 1에 1을 올려주고, 2번째 자릿수에서 1인 경우는 1가지 있었으니, 0 과 2에 1을 추가해주는 식으로 자릿수별로 각각의 -1, +1값을 다음 자릿수의 자리에 추가해주면 총 몇가지의 경우가 올 수 있는지 구할 수 있습니다.

 

여기서 1000000000을 나눠서 arr의[i][k]값을 넣어주는데 이렇게 되면, 각 자릿수별로 나머지 값들이 들어가게 됩니다.

마지막에 출력시에도 모든 [k]값들을 (각 자릿수별 가짓수를) 더해서 내주게 되는데 이때에도 1000000000으로 나누어줘야합니다.

예를들어 10으로 나눠서 내는 경우라면, 우리가 arr[i][k]에 각각 나머지값의 최대값인 9를 넣었다고 하면, 9+9+9를 내게 되는데, 이는 우리가 구하고자하는 값이 아닙니다.

반드시 다시 10으로 나누어주어서 27%10= 7로 출력값이 7이 되게 해주어야합니다.

10으로 나눈 값을 구하라고 했는데, 10보다 훨씬 큰 27을 출력하면 안되겠죠?

이 부분도 꼭 놓치지 말아야하는 포인트 같습니다.

 

var fs = require('fs');
var inputs = fs.readFileSync('/dev/stdin').toString();
inputs = Number(inputs);
var arr = [];
arr[0] = [];
arr[1] = new Array(10).fill(1);
arr[1][0] = 0;
for(var i=1; i<inputs; i++){
    arr[i+1] = new Array(10).fill(0);
    arr[i+1][1] += arr[i][0] % 1000000000;
    for(var k=1; k<arr[i].length-1; k++){
        arr[i+1][k-1] += arr[i][k] % 1000000000;
        arr[i+1][k+1] += arr[i][k] % 1000000000;
    }
    arr[i+1][8] += arr[i][9] % 1000000000;
}
console.log(arr[inputs].reduce((a,v)=>a+v, 0) % 1000000000);