[백준 11057번] 오르막 수

 

항상 점화식을 먼저 생각하고

dp[i]를 dp[i-1]로 표현하는 방식을 생각해야함.

 

주의사항 : divisor가 있다면 모두다 나눠주는게 좋음

 

 

 

1. 점화식

dp[i][j] = dp[i-1][0] +dp[i-1][1] + ... dp[i-1][j]

 

2. 코드

#include <stdio.h>

int d = 10007;
int main()
{
    int n;
    scanf("%d", &n);

    unsigned long long dp[1001][10] = {};

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

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

    unsigned long long sum = 0;
    for (int i = 0; i <= 9; i++) 
    {
        sum += dp[n][i]%d;
    }
    printf("%d", sum%d);

    return 0;
}