[백준 11057] 오르막 수

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

숫자가 5287과 같이 존재할 때 5를 1번째 자리 숫자 2를 2번째 자리숫자 8을 3번째 자리숫 7을 4번째 자리 숫자로 표현할 수 있다.

n번째 숫자가 i라면(0<= i <=9) n+1번째 숫자는 i부터 9까지, 9-i+1가지 경우가 존재할 수 있다.

역으로 n+1번째 숫자가 i일 수 있는 경우의 수는 n번째 숫자가 i와 같거나 작을 수 있는 경우의 수의 합이다.

n+1번째 숫자가 i일 수 있는 경우의 수 <- n번째 숫자가 0일 때 경우의수 + n번째 숫자가 1일 때 경우의수 + ... + n번째 숫자가 i일 때 경우의수

길이가 N인 오르막수 개수는 N번째 자리가 0일 때 경우의 수부터 9일 때 경우의 수까지 모두 더하면 된다.

점화식

[n][i] : n번째 숫자가 i일 때 경우의 수

[1][0:9] <- 1

[n][0] <- [n-1][0]

[n][1] <- [n-1][0] + [n-1][1]

...

[n][9] <- [n-1][0] + ... + [n-1][9]

C++ code

n번째 숫자의 경우의 수를 구하기 위해서는 n-1번째 숫자의 경우의 수만 필요하고 그 이전 정보는 필요 없으므로

2행 배열을 사용하여 한 행씩 번갈아가며 정보를 갱신할 수 있다. 

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int arr[2][10];
    for(int i = 0; i < 10; i++){
        arr[0][i] = 1;
    }
    for(int i = 0; i < 10; i++){
        arr[1][i] = 0;
    }
    int k = 0;
    for(int i = 1 ; i < n; i++){
        k = !k;
        for(int j = 0; j < 10; j++){
            arr[k][j] = 0;
            for(int l = 0; l <= j; l++){
                arr[k][j] = (arr[k][j] + arr[!k][l]) % 10007;
            }
        }
    }
    int answer = 0;
    for(int i = 0; i < 10; i++){
        answer = (answer + arr[k][i]) % 10007;
    }
    cout << answer;
    return 0;
}