[BOJ] 11057번 오르막 수 c++

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

문제
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

---

입력 1
1

출력 1
10

---

입력 2
2

출력 2
55

---

입력 3
3

출력 3
220

---

#include <cstdio>
#include <algorithm>
#include <numeric>
using namespace std;

int main() {
  int N;
  int dp[1001][10] = {0,}; // dp[x][y] == x단계에서 끝자리가 y인 경우

  scanf("%d", &N);
  for(int i = 0; i < 10; i++)
    dp[1][i] = 1;

  for(int i = 2; i <= N; i++) {
    for(int j = 0; j < 10; j++) {
      for(int k = 0; k <= j; k++) {
        dp[i][j] += dp[i - 1][k];
      }
      dp[i][j] %= 10007;
    }
  }

  printf("%d\n", accumulate(dp[N], dp[N] + 10, 0));
}

예전에 비슷한 문제를 풀었던 거 같은데 풀다가 막혀서 다른 풀이를 찾아보았다.
우선 배열 dp를 이차원 배열로 선언한다. 첫번째 인덱스는 오르막 수의 총 자릿수이고, 두번째 인덱스는 오르막 수의 가장 끝에 오는 숫자를 가리킨다.

• 임의의 x와 y가 주어졌을 때 오르막의 수는, x - 1 길이의 오르막 수에서 끝자리가 y보다 작거나 같은 모든 경우의 합이다.
• 수가 커지지 않게 모듈로 연산한 값을 저장해준다.