백준 11057: 오르막수

문제 링크 : https://www.acmicpc.net/problem/11057

11057번: 오르막 수

 문제설명 

 

앞자리수가 뒷자리수보다 작거나 같은 수를 오르막수라고함 예를들면 11 12 13 18 126 이런숫자.

숫자의 길이가 주어졌을때 오르막 수의 개수를 구하는것 .

 

 알고리즘 

 

1. 배열을 만듦 arr[i][j]  여기서 i는 자리수고 j는 숫자. 예를들면 arr[1][7] 이면 첫번째 자리수는 7 요런느낌 

2. 점화식 : arr[i][j] = arr[i][0]+...+arr[i][j] 이걸 적용하여서 풀면되는데 설명을 못하겠네..

 

코드로 보자..

 

 코드 

#include<iostream>
 
using namespace std;
 
int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(0);
 
    int dp[1001][10];
    int n;
    cin >> n;
    
    //1번째 자리수 1로 초기화
    for (int i = 0; i < 10; i++)dp[1][i] = 1;
 
    //나머지는 0으로 초기화
    for (int j = 2; j <= n; j++) 
        for (int i = 0; i < 10; i++)dp[j][i] = 0;
 
    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][j] + dp[i - 1][k]; 
                dp[i][j] = dp[i][j] % 10007;
            }
        }
    }
    
    int sum = 0;
 
    //마지막에 n번째 자리수 오르막수를 다더함
    for (int i = 0; i < 10; i++) {
        sum = sum + dp[n][i];
        sum %= 10007;
    }
 
    cout << sum;
 
}