2022.02.07 [백준] C# 쉬운 계단 수

 

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

10844번: 쉬운 계단 수

 

---

풀이

이 문제는 이전의 숫자에 따라 갯수가 달라진다. 이전의 마지막 숫자가 0이면 다음에는 1만 나올 수 있고, 9도 마찬가지로 8만 나올 수 있다. 0, 9를 제외하면 1~8까지는 2개의 숫자가 나올 수 있다. 이 규칙을 코드로 옮기면 아래와 같다.

using System;
using System.Text;
using System.IO;
 
class Program
{
    static int[,] num;
 
    static void Cal(int n)
    {
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                if (j == 0)
                {
                    num[i, j] = num[i - 1, 1];
                }
                else if (j == 9)
                {
                    num[i, j] = num[i - 1, 8];
                }
                else
                {
                    num[i, j] = num[i - 1, j - 1] + num[i - 1, j + 1];
                }
                num[i, j] %= 1000000000;
            }
        }
    }
 
    static void Main()
    {
        StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
        StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));
        StringBuilder sb = new StringBuilder();
        int n = int.Parse(sr.ReadLine());
        num = new int[n, 10];
        for(int i = 1; i < 10; i++)
        {
            num[0, i] = 1;
        }
        Cal(n);
        int sum = 0;
        for(int i = 0; i < 10; i++)
        {
            sum += num[n - 1, i];
            sum %= 1000000000;
        }
        sw.WriteLine(sum);
        sr.Close();
        sw.Close();
    }
}