[백준] 쉬운 계단 수

문제

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

고민

45656, 3234545 처럼 인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다.

N이 주어지면 길이가 N인 계단 수는 총 몇개가 있는지 구한 뒤 1,000,000,000으로 나눈 나머지를 출력한다.

단, 0으로 시작하는 수는 세지 않는다.

 

처음엔 경우의 수를 다 만들어 봐야하나? 생각했지만 알고리즘 분류가 DP였다.

DP는 이전에 계산했던 수를 저장해두고 필요할 때 다시 가져와서 불필요한 추가 연산을 없애는 알고리즘이다.

 

그렇다면 일단 경우의 수를 따져봐야한다.

1. 길이가 1일 때 계단 수는?

1, 2, 3, 4, 5, 6, 7, 8, 9

 

2. 길이가 2일 때 계단 수는?

10 | 01 | 12 | 23 | ... | 78 | 89

     | 21 | 32 | 43 | ... | 98 | 

 

3. 길이가 3일 때 계단 수는?

010 | 101 | 012 | 123 ... | 678 | 789

210 | 121 | 212 | 323 ... | 878 | 989

       | 021 | 232 | 343 ... | 898 | 

                | 432 | 543 ... |  

 

0으로 시작하는 수를 제외하고(취소선) 경우의 수를 만들었다. 규칙을 살펴보면

길이가 3이고 마지막 자릿수가 2인 계단 수를 보면 212, 232, 432가 있다.

길이가 2이고 마지막 자릿수가 1인 계단 수 + 길이가 2이고 마지막 자릿수가 2인 계단수이다.

 

212는 21에 마지막 자리 2를 추가해서 212

232는 23에 마지막 자리 2를 추가해서 232

432는 43에 마지막 자리 2를 추가해서 432

 

위 방법이 엥? 싶은데 실세로 표를 그렸을 때 맞는 수대로 선을 그어보면 이진트리처럼 나오는데, 이게

[i-1][j-1]이랑 [i-1][+1] 방식을 적용 가능한 그림이 나온다. (이 그림 4번 그리고 나서야 이해함)

 

아래는 코드~.~

코드

참고로 dp[][]의 의미는 [길이][마지막 자릿수]이다.

예를들어 dp[2, 3]이면 2길이의 마지막 자릿수가 3인 것을 의미한다.

 

그리고 만약 마지막 자리가 0이거나 9이면 제한을 걸어줘야한다.

우린 -1이나 10이 없기때문이다.

그러면 0일땐 [i-][j+1]만 해주고 9일땐 [i-1][j-1]만 해주면 된다.

해당 조건이 아래 2중 for문 안에 if문 2개이다.

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

namespace DP
{
    internal class 쉬운계단수
    {
        const int MOD = 1000000000;
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            long[,] dp = new long[n + 1, 10];

            // 길이가 1인 계단 수는
            // 1부터 9까지 하나씩 존재
            for (int j = 1; j < 10; j++)
            {
                dp[1, j] = 1;
            }

            // dp 채우기
            for(int i = 2; i <= n; i++)
            {
                for(int j = 0; j < 10; j++)
                {
                    if(j > 0)
                    {
                        dp[i, j] += dp[i - 1, j - 1];
                    }
                    if(j < 9)
                    {
                        dp[i, j] += dp[i - 1, j + 1];
                    }

                    dp[i, j] %= MOD;
                }
            }

            // 결과
            long result = 0;
            for(int j = 0; j < 10; j++)
            {
                result += dp[n, j];
            }

            result %= MOD;

            Console.WriteLine(result);
        }
    }
}