10844) 쉬운 계단수

문제요약

계단 수란, 좌우에 위치한 수가 단 1만 차이나는 수를 의미(예. 12345 4564)
입력한 수의 길이에 해당하는 계단 수가 몇개 있는지를 출력해야 한다.

풀이

0부터 9까지의 숫자로 끝나는 수가 몇개인지를 구하여 총 경우의 수를 구하였다. 먼저, 1자리 수는 1부터 9까지로 9가지 경우의 수, 2자리 수는 0,1,9로 끝나는 경우의 수 1개 그리고 나머지 2부터 8까지 2개씩 해서 총 17개.
규칙성을 살펴보면, 각 수로 끝나는 수의 갯수는 이전 자릿수에서 발생된 -1, +1의 수들의 값에 영향을 받는다.
예시: 3자리 계단수 중 1로 끝나는 계단수의 갯수 = 2자리 계단수 중 0으로 끝나는 계단수 갯수+2로 끝나는 계단 수
즉, n자리 계단수 중 m으로 끝나는 계단수의 갯수를 P(n, m)라고 한다면,
P(n, m) = P(n-1,m+1) + P(n-1, m-1)

코드

#include<iostream>
using namespace std;

int main(){
    int num;

    //while(true){
    cin>>num;
    int **result = new int*[num];
    int first_arr[11]= {0,1,1,1,1,1,1,1,1,1,0};
    for(int i=1;i<num;i++){
        result[i] = new int[11];
    }
    result[0] = first_arr;

    for(int i=1;i<num;i++){
       for(int j=0;j<10;j++){
        if(j == 0)
        result[i][j] = result[i-1][1]%1000000000;
       
       else if(j ==9)
       result[i][j] = result[i-1][8]%1000000000;

      else
       result[i][j] = (result[i-1][j-1]+result[i-1][j+1])%1000000000;
    
       }
    }
    int sum =0;
    for(int i = 0;i<10; i++)
        sum = (sum+result[num-1][i])%1000000000;
    cout<<sum<<endl;
    delete[] result;

   // }
    return 0;
}