[백준/C++] 11057번_오르막 수

문제는 다음과 같습니다.

제가 푼 과정은 다음과 같습니다.
먼저, 2차원 배열 dp[idx][num]을 이용했고,

• idx: 숫자의 자릿수를 의미함
• num: 자릿수에 해당하는 수를 의미함

789이라는 수를 예로 들면,

7-> idx:1, num:7
8-> idx:2, num:8
9-> idx:3, num:9

을 의미합니다.

점화식이 생각보다 구하기 쉬운데, 점화식은 다음과 같습니다.

dp[idx][num] += Σ(i : 0~num) dp[idx-1][i]

이 전 자리의 수는 현재 수보다 작거나 같기만 하면 되므로,
i의 범위는 0부터 ~ num까지입니다.

또한, 2차원 dp배열의 초기 세팅은 다음과 같습니다.
dp[1][0]=1; dp[1][1]=1; ... dp[1][9]=0; 입니다.

또한 구하는 수의 길이가 N일때 오르막 수의 개수는
Σ(i=0~i=9)dp[N][i] 입니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long dp[1001][10]={0, };
    long long mod = 10007;
    int n; cin>>n;

    for(int i=0; i<=9; i++) dp[1][i]=1;

    for(int i=1; i<=n; i++){
      for(int j=0; j<=9; j++){
        for(int k=0; k<=j; k++){
          dp[i][j] += dp[i-1][k];
        }
        dp[i][j]%=mod;
      }
    }

    long long res = 0;
    for(int i=0; i<=9; i++) res+=dp[n][i];
    cout<<res%mod<<"\n";
    return 0;
}