백준 10844번 쉬운 계단 수 JAVA

링크텍스트

설명

예: N=1
1,2,3,4,5,6,7,8,9 → 9개

예: N=2
10,12,21,23,32,34,43,45,54,56,65,67,76,78,87,89,98 → 17개

시간복잡도: O(N), 공간복잡도: O(N)

회독

• [ x ] 1회
• 2회
• 3회

코드

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

public class Main {
        static final int MOD = 1_000_000_000;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        long [][] dp = new long[n+1][10]; //길이가 n이고 마지막 숫자가 d인 갯수

        for(int j=1;j<10;j++){
            dp[1][j] = 1;
        }

        for(int i=2;i<=n;i++){
            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 answer = 0;
        for(int i=0;i<10;i++){
            answer+=dp[n][i];
        }

        System.out.println(answer%MOD);
    }
}

참고 글

https://st-lab.tistory.com/134