백준 11057번 오르막 수 (C++)

문제 링크 : www.acmicpc.net/problem/11057

11057번: 오르막 수

이 문제는 백준 10844번 쉬운 계단 수와 거의 동일한 유형의 문제이다.

쉬운 계단 수의 문제와 차이점은, 이 문제는 쉬운 계단 수의 문제와 달리 +-1차이의 계단수만 더해주면 되는게 아니라 어떤 계단보다 작은 수의 계단들의 총합을 모두 더해줘야한다는 점이다.

이 점을 빼면 쉬운 계단 수와 별 차이가 없는 문제이니, 자세한 설명은 생략한다.

 

#include <iostream>
#define MAX 1001
#define MOD 10007
using namespace std;

long long arr[MAX][10];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    long long ans = 0;
    cin >> n;
    for(int i=0; i<10; i++) arr[1][i] = 1;
    for(int i=2; i<=n; i++){
        for(int j=0; j<10; j++){
            for(int x=0; x<=j; x++){
                arr[i][j] += arr[i-1][x];
            }
            arr[i][j] %= MOD;
        }
    }
    for(int i=0; i<10; i++) ans += arr[n][i];
    cout << ans % MOD << "\n";
    return 0;
}