C# 10844번 쉬운 계단 수

코드 : 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Numerics;

namespace _5
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = Convert.ToInt32(Console.ReadLine());

            long[,] arr = new long[10, 101];

            long sum = 0;
            
            //초기값
            for (int i = 0; i < 10; i++)
            {
                arr[i, 1] = 1;
            }

           

            for (int i = 2; i <= N; i++)
            {
                for (int j  = 0; j < 10; j++)
                {
                    if(j == 0)
                    {
                        arr[j, i] = arr[j+1, i-1];
                    }
                    else if (j == 9)
                    {
                        arr[j, i] = arr[j - 1, i - 1] ;
                    }
                    else
                    {
                        //미리 나눠서 넣어주지 않으면 값을 초과하기 때문에 정확한 값이 들어가지 않는다.
                        arr[j, i] = (arr[j - 1, i - 1] + arr[j + 1, i - 1 ]) % 1000000000;
                    }
                }
            }

            for (int i = 1; i < 10; i++)
            {
                sum += arr[i, N];
            }

            Console.WriteLine(sum % 1000000000);

        }
    }
}

문제 풀이 :

규칙을 잘 찾아보면 길이가 N이고 0으로 시작하는 계단 수는 N-1의 1로 시작하는 계단 수에서 앞에 0이 붙은 꼴이다. 

9로 시작하는 계단 수 역시 N-1의 8로 시작하는 계단 수 앞에 9가 붙은 꼴이다.

나머지는 1부터 8까지를 i라고 할때 길이가 N인 i의 갯수는 N-1의 i-1의 갯수와 i+1의 갯수의 합과 같다.

즉 점화식은 다음과 같다

점화식

 

아래와 같은 방식의 배열이 나와야하며 0으로 시작하는 것은 제외한다했으니 이를 제거해주기만 하면 된다.