오르막 수 백준 11057

문제

오르막 수 백준 11057번

리뷰

'쉬운 계단 수' 문제 보다 고려할 것이 적었다.

숫자가 반드시 1씩 연속되어야 하는것도 아니고, 인접한 수가 같아도 오름차순으로 친다.

ex) 2234, 3678, 11119

[ 점화식 ]

자리수 N의 숫자들의 마지막 자리 숫자가 L이라고 한다.

**arr [2] [3] 은 2자리 숫자 중에 마지막 자리 숫자가 3인 계단 수의 개수다. ex) 13, 23, 33

arr [N] [L] 을 구할 때, arr[N-1] [k]의 개수를 누적하는데, 이 때 k는 0부터 j이다.

2자리 숫자들 중에 마지막 자리 숫자가 '7' 이라면, k는 0부터 7까지다.

arr [N] [L] = arr [N-1] [0] + arr [N-1] [1] + arr [N-1] [2] + ... + arr [N-1] [6] + arr [N-1] [k]

오르막 수는 0부터 시작 가능하다.

코드

#include <stdio.h>
using namespace std;

// 오르막 수  (BOJ 11057) 

int arr[1001][10];

int main(void){

    freopen("input.txt", "rt", stdin);

    int n = 0, i = 0, j = 0;
    int sum = 0;

    scanf("%d", &n);

    for(i = 0; i <= 9; i++){ // 1자리 수는 전부 1개  
        arr[1][i] = 1;
    }

    for(i = 2; i <= n; i++){

        for(j = 0; j <= 9; j++){ // 0 부터 시작 가능 

            for(int k = 0; k <= j; k++){ 
                // j=3 이라면, 마지막 수k로 0, 1, 2, 3 올 수 있다.  
                arr[i][j] += arr[i-1][k];
            }    

            arr[i][j] %= 10007;
        }    
    }

    for(i = 0; i <= 9; i++){
        sum += arr[n][i];
    }    

    printf("%d", sum % 10007);

    return 0;
}