BOJ : 10844 쉬운계단수 (JS)

소스코드

let fs = require('fs'); 
const filePath = process.platform === `linux` ? `/dev/stdin` : `예제.txt`; 
let input = fs.readFileSync(filePath).toString().split(' ');
const c = console.log

n = Number(input[0])


let dp = []

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

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

for (let i = 2 ; i < n+1 ; i++){
    for (let j = 0 ; j < 10 ; j++){

        if (j === 0){
            dp[i][j] = (dp[i-1][1]) % 1000000000
        } 
        else if (j === 9) {
            dp[i][j] = dp[i-1][8] % 1000000000
        }
        else {
            dp[i][j] = ((dp[i-1][j+1]) + (dp[i-1][j-1])) % 1000000000
        }
    }
}

add = (dp) =>{
    return dp.reduce((a,b) => a+b,0)
}

c((add(dp[n]) % 1000000000))

 

풀이

일단 2차원배열을 생성해준 후 dp[i][j] 에서 i = 자릿수, j = 마지막에 올 숫자로 정해줍니다.
1자리수 일때는 1,2, ... , 9 이므로 이므로 dp[1][1] = 1 ... dp[1][9] = 1 이라 해줍니다.

 

그 후 dp[2][0] 은 10인 경우 밖에 없으므로 dp[1][1] 의 값을 넣어줍니다

2 같은 경우에는 끝자리1에서 나오고 3에서도 나올 수 있으니 dp[1][1] + dp[1][3] 이라는 식을 얻게 됩니다.

점화식을 이용하면 dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이라는 식을 얻습니다.

 

9는 89인 경우 밖에 없으므로 dp[1][8] 의 값을 넣어줍니다.

 

문제

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

10844번: 쉬운 계단 수