[Baekjoon] 11057번: 오르막 수 / dynamic

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

11057번: 오르막 수

오르막수는 인접한수가 같아도 오름차순으로 치고, 0부터 시작 가능하므로,
수의 길이가 1일때, 자기 자신 수 0,1,2,3,4,5,6,7,8,9로 10개,
수의 길이가 2일때,

00, 01, 02, 03, 04, 05, 06, 07, 08, 09 -> 10개 11, 12, 13, 14, 15, 16, 17, 18, 19 -> 9개 ...
99 -> 1개
다 더하면 1+2+3+4+5+6+7+8+9+10으로 55개이다.

수의 길이가 3일때는, 000, 001, 002, 003, 004, 005, 006, 007, 008, 009 -> 10개 011, 012, 013, 014, 015, 016, 017, 018, 019 -> 9개 ... 099 -> 1개 : 여기까지 55개 111, 112, 113, 114, 115, 116, 117, 118, 119 -> 9개 ... 199 -> 1개 : 여기까지 45개 즉, 1+3+6+10+15+21+28+36+45+55 (수의 길이가2일때의 누적 합) = 220이다.

마찬가지로 수의길이가 4일때는 수의길이가 3일때의 누적 합 1+4+10+10+20+35+56+84+120+165+220 = 715
수의길이가 n일때 오르막수는 수의길이 n-1일때 누적 합을 구하면 된다.

코드

//11057
#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, const char * argv[]) {
    cin.tie(NULL);
    ios::sync_with_stdio(0);

    int N;
    long long up[1010][11];
    for(int i=1;i<=10;i++) up[1][i] = i;

    cin >> N;
    for(int i=2;i<=1001;i++){
        for(int j=1;j<=10;j++){
            up[i][j] = (up[i][j-1] + up[i-1][j])%10007;
        }
    }

    cout << (up[N][10])%10007;

    return 0;
}