[백준] 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

 

계단 수 : +1, -1

N번째 자릿수의 개념 

ex ) 54321

첫번째 자릿수 : 1

두번째 자릿수 : 2

...

다섯번째 자릿수 : 5

 

• N번째 자릿수의 값이 0인 경우 : 1만 가능
• N번째 자릿수의 값이 9인 경우 : 8만 가능
• 그 외 1~ 8은 +1, -1가능

 

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws Exception {
        long mod = 1000000000;
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        long[][] dp = new long[N+1][10];

        // 첫 번째 자릿수: 경우의 수 1개
        for(int i = 1; i < 10; i++) {
        	dp[1][i] = 1;
        }

        // 두번째 자릿수부터 N까지 탐색
        for(int i = 2; i <= N; i++) {
            // i번째 자릿수의 값 탐색 : 0~9
            for(int j = 0; j < 10; j++) {

                if(j == 0) {
                	dp[i][0] = dp[i-1][1] % mod;
                } else if(j == 9) {
                	dp[i][9] = dp[i-1][8] % mod;
                } else {
                	dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
                }
            }
        }

        long ans = 0;
        for(int i = 0; i < 10; i++) {
        	ans += dp[N][i];
        }

        System.out.println(ans % mod);
    }
}