[백준][DP] 오르막 수

1. 문제 주소

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

11057번: 오르막 수

2. 문제

수의 길이가 n일 때 n번째 숫자로 각각 0~9가 올 수 있는 경우를 나누어 생각하면 쉽게 풀 수 있다.

3. 소스코드

#include <iostream>
using namespace std;
int dp[1001][10];
 
int main() {
    
    int n;
    cin >> n;
 
    for (int j = 0; j < 10; j++)
        dp[1][j] = 1;
 
    for (int i = 2; i <= n; i++) {
        dp[i][0] = dp[i - 1][0];
        for (int j = 1; j < 10; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j] % 10007;
        }
    }
    int result = 0;
    for (int j = 0; j < 10; j++)
        result += dp[n][j];
    cout << result % 10007 << '\n';
    return 0;
}