[Algorithm] Baekjoon 11057번 : 오르막 수

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

11057번: 오르막 수

#define MOD 10007
 
int n;
int dp[1001][10] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < 10; ++i)
    {
        dp[1][i] = 1;
    }
 
    for (int i = 2; i <= n; ++i) // n자릿수만큼만
    {
        for (int j = 0; j <= 9; ++j)
        {
            for (int k = j; k <= 9; ++k)
            {
                dp[i][j] = (dp[i][j] % MOD + dp[i - 1][k] % MOD) % MOD;
            }
        }
    }
 
    int answer = 0;
 
    for (int i = 0; i <= 9; ++i)
    {
        answer = (answer % MOD + dp[n][i] % MOD) % MOD;
    }
 
    cout << answer;
}

 

이 문제에서의 규칙은 아래와 같다.

 

000 001 002  ...... 009

 

011 012 013 .... 019..

 

즉, n번째 자릿수의 값이 만약 1이라면 dp테이블을 돌며 n-1번째의 1이상인 값들을 합산해주면 된다.

MOD연산은 저렇게 까지 안해도 될 수도 있지만, 저 방법이 제일 정석적인 방법이다.

(A + B) % MOD -> (A%MOD + B%MOD)%MOD