BOJ 10884 쉬운 계단 수

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

문제 분석

---

문제 해결의 실마리 찾기

너무 중복이 많다! 어차피 뒤에 올 숫자는 정해져있는데...

길이가 len 이면서, startNum으로 시작하는 수의 개수는?

row=len,col=startNum	0	1	2	3	4	5	6	7	8	9
0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0	0	0
4	0	0	0	0	0	0	0	0	0	0
5	0	0	0	0	0	0	0	0	0	0
6	0	0	0	0	0	0	0	0	0	0
7	0	0	0	0	0	0	0	0	0	0
8	0	0	0	0	0	0	0	0	0	0
9	0	0	0	0	0	0	0	0	0	0

구현

---

실패한 문제풀이

---

성공한 문제풀이

---

const dir = process.platform === 'linux' ? 'dev/stdin' : 'test.txt'

const N = require('fs').readFileSync(dir).toString().trim() * 1

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

for (let len = 1; len < N + 1; len++) {
  for (let startingNum = 0; startingNum < 10; startingNum++) {
    const left = startingNum - 1
    const right = startingNum + 1
    if (left >= 0) {
      dpTable[len][startingNum] += dpTable[len - 1][left]
    }
    if (right < 10) {
      dpTable[len][startingNum] += dpTable[len - 1][right]
    }
    dpTable[len][startingNum] %= 1000000000
  }
}

const sum = (dpTable[N].reduce((prev, curr) => prev + curr, 0) - dpTable[N][0]) % 1000000000
console.log(sum)