[백준 10844] 쉬운 계단 수

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

45656 이라는 숫자가 존재한다고 할때 4는 1번째 자리 수, 5는 2번째 자리 수 6은 3번째 자리 수, 5는 4번째 자리 수, 6은 5번째 자리 수로 표현할 수 있다.

n번째 자리 수가 0일경우 n+1번째 자리수는 1만 가능하며 n번째 자리 수가 9일 경우 n+1번째 자리수는 8만 가능하다.

n번째 자리 수가 1~8인 경우는 n+1번째 자리수에 각각 2개의 숫자가 존재할 수 있다. (예: n번째 자리 수가 1인경우 0 또는 2, n번째 자리 수가 4인경우 3 또는 5)

즉,

n+1번째 자리에서 0이 나올 수 있는 경우의 수 <- n번째 자리에서 1이 나올 수 있는 경우의 수

n+1번째 자리에서 1이 나올 수 있는 경우의 수 <- n번째 자리에서 0이 나올 수 있는 경우의 수 + n번째 자리에서 2가 나올 수 있는 경우의 수

...

n+1번째 자리에서 8이 나올 수 있는 경우의 수 <- n번째 자리에서 7이 나올 수 있는 경우의 수 + n번째 자리에서 9이 나올 수 있는 경우의 수

n+1번째 자리에서 9가 나올 수 있는 경우의 수 <- n번째 자리에서 8이 나올 수 있는 경우의 수

마지막에 N번째 자리에서 0~9가 나올 수 있는 경우의 수를 모두 더하면 길이가 N인 계단 수가 된다.

점화식

arr[1][0] = 0

arr[1][1:9] = 1

arr[n][0] = arr[n-1][1]

arr[n][1] = arr[n-1][0] + arr[n-1][2]

arr[n][2] = arr[n-1][1] + arr[n-1][3]

arr[n][3] = arr[n-1][2] + arr[n-1][4]

arr[n][4] = arr[n-1][3] + arr[n-1][5]

arr[n][5] = arr[n-1][4] + arr[n-1][6]

arr[n][6] = arr[n-1][5] + arr[n-1][7]

arr[n][7] = arr[n-1][6] + arr[n-1][8]

arr[n][8] = arr[n-1][7] + arr[n-1][9]

arr[n][9] = arr[n-1][8]

C++ code

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

행 2개만 사용하여 번갈아가며 정보를 저장할 수 있다.

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