[백준 11057번] 오르막 수

풀이

---

1일 때 -> 0 1 2 3 4 5 6 7 8 9

2일 때 -> 01 02 03 04 05 06 07 08 09

             12 13 14 15 16 17 18 19

             23 24 25 26 27 28 29

                :

             78 79

             89

3일 때 -> 001 002 003 004 005 006 007 008 009

             012 013 014 015 016 017 018 019

                :

             779 789

             889

규칙

1 -> 10

2 -> 10 + 9 + 8 + 7 + ...... + 3 + 2 + 1  = 55

3 -> 55 + 45 + 36 + ...... + 1 = 220

하나씩 증가할수록 이전에 계산한 총합부터 계산해야한다.

10007으로 나눈 나머지를 계산해야 하므로 숫자가 커지게되면 %10007을 해주어야 한다.

소스 코드

---

#include <iostream>
using namespace std;
 
int main() {
    int n;
    long long dp[11],sum=0,copy[11];
    cin >> n;
    if (n == 1) {
        cout << 10;
        return 0;
    }
    for (int i = 1; i <= 10; i++) {
        dp[i] = i;
        copy[i] = dp[i];
        sum += dp[i];
    }
    for (int a = 2; a < n; a++) {
        copy[10] = sum;
        for (int b = 9; b >= 1; b--) {
            copy[b] = (copy[b + 1] - dp[b + 1]);
        }
        for (int b = 1; b <= 10; b++) {
            dp[b] = copy[b] % 10007;
        }
        sum = 0;
        for (int b = 1; b <= 10; b++) {
            sum = (sum+dp[b]);
            
        }
    }
    cout << sum % 10007;
    return 0;
}