11057 오르막 수

문제 분석

끝자리수\글자수	한 글자(1)	두 글자(2)	세 글자(3)
0	1	1	1
1	1	2	3
2	1	3	6
3	1	4	...
4	1	5	...
5	1	6	...
6	1	7	...
7	1	8	...
8	1	9	...
9	1	10	...

표 해설

1. 한 글자로 표현할 수 있는 수 중에, 끝자리가 0인 오르막 수의 개수는 1개, 끝자리가 1인 수의 개수는 1개, 끝자리가 2인 수의 개수는 1개, …

2. 두 글자로 표현할 수 있는 수 중에, 끝자리가 0인 오르막 수의 개수는 1개(00), 끝자리가 1인 수의 개수는 2개(01, 11), 끝자리가 2인 수의 개수는(02, 12, 22), …

3. 표를 잘 살펴보면 다음과같이 패턴을 찾아낼 수 있다.

   

   이를 이차원배열 memo가 있다고 가정하여 memo[글자수(n)][끝자리수(i)] 라고 생각해보면, 다음과 같이 점화식을 작성할 수 있다.

   memo[n][i] = memo[n][i - 1] + memo[n-1][i]

풀이

const N = +require('fs').readFileSync('dev/stdin');
const memo = [new Array(10).fill(1)];

let mod = 10007;

for (let n = 1; n < N; n++) {
  memo[n] = new Array(10);

  for (let i = 0; i <= 9; i++) {
    memo[n][i] = (memo[n][i - 1] || 0) + memo[n - 1][i];
    memo[n][i] %= mod;
  }
}

let answer = 0;
for (let i = 0; i <= 9; i++) {
  answer += memo[N - 1][i];
}
console.log(answer % mod); // 오라막 수를 10007으로 나눈 나머지

공간 복잡도

O(n²)