[백준][11057번][DP] 오르막 수

오르막수

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

<코드>

#include <stdio.h>
#define mod 10007
 
int main(void){
    int N;
    int number[1001][10] = {};
    int total = 0;
 
    scanf("%d", &N);
 
    for (int i = 0; i < 10; i++)
        number[1][i] = 1;
 
    for (int i = 2; i <= N; i++)
        for (int j = 0; j < 10; j++)
            for (int k = j; k < 10; k++)
                number[i][j] = (number[i][j] + number[i - 1][k]) % mod;
 
    for (int i = 0; i < 10; i++)
        total = (total + number[N][i]) % mod;
 
    printf("%d\n", total);
 
    return 0;
}

<문제 푼 요령>

1. 이 문제는 한번에 우리가 원하는 자릿수를 구하는게 아니고 차근차근 자릿수를 올려가면서 구하면 될 거 같다 마치 피보나치 수열을 구하는 것 처럼

2. 현재의 j 자릿수에 앞의 숫자가 i 라고 했을 때 이 숫자는 j-1 자릿수의 앞자리가 i 보다 크거나 같은 값으로 만들 수 있다.

3. 이를 우리가 원하는 N자리수 까지 반복한다면 우리는 정답을 구할 수 있다.