쉬운 계단 수

📍 문제 설명

 

 

💡 접근

0, 9를 제외한 숫자를 제외하고는 2개를 더해줄 수 있다.

 

 

👩‍💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static long mod = 1000000000;
    static int n, m, answer;
    static int[][] board;
    static long[][] arr, dp;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        //BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = kb.nextInt();
        dp = new long[n+1][10];

        //첫번째 자릿수는 1로 초기화한다.
        for(int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }

        T.solution();

        long result = 0;

        for(int i = 0; i < 10; i++) {
            result += dp[n][i];
        }
        System.out.println(result);

    }

    private void solution() {
        //두번째 자릿수부터 확인
        for(int i = 2; i <= n; i++) {
            //i번째 자릿수의 숫자들 탐색
            for(int j = 0; j < 10; j++) {
                //10이면 101 20이면 201
                if(j == 0) {
                    dp[i][0] = dp[i-1][1] % mod;
                }
                //19면 198 29면 298
                else if(j == 9) {
                    dp[i][9] = dp[i-1][8] % mod;
                }
                //15면 154 156 둘다 가능
                else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;
                }
            }
        }
    }

}