백준 10844 쉬운 계단 수 (JAVA)

백준 10844 쉬운 계단 수

백준10844

접근방법

이 문제는 dp문제다. 2차원 배열생성 후 dp[길이][마지막 자리수가 계단이 되는 경우의 수] 로 접근해야 한다.

N==1 즉 길이가 1일때

dp[1][1]1길이가 1이고 끝자리의 수가 1일때 앞에 올 수 있는 수는 없으므로 경우의 수는 1이다.

dp[1][2]1길이가 1일이고 끝자리의 수가 2일때 앞에 올 수 있는 수는 없으므로 1이다. - n=1, 즉 길이가 1일때 끝자리수가1-9이면 앞에 올 수 있는 수가 없으므로 각각 경우의 수는 1이다.

N==2 즉 길이가 2일때(10~99)

dp[2][0] 길이가 2이고 끝 자리수가 0일때 앞에 올 수 있는 수는 1뿐이다. 따라서 dp[2][0] = dp[1][1] 즉 자리수가 1일때 끝에 1이 오는 경우의 수 이다.

dp[2][9] 일때 앞에 올 수 있는 수는 8 뿐이다. 따라서 dp[2][9] = dp[1][8] 이 성립한다.

그 이외의 dp[2][2~8]일때 dp[2][2] = dp[1][1] + dp[1][3] 이런식으로 dp[2][8] = dp[1][7]+dp [1][9] 가 성립한다.

code

```java
import java.util.Scanner;

public class Main {

    static long mod= 1000000000L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long[][] dp = new long[n+1][10];
//자리수가 1일때는 끝자리가1~9일때 모두 경우의 수가 1이므로 dp[1][1~9]를 모두 1로 초기화한다.
        for (int i = 1; i <= 9; i++) { 
            dp[1][i]=1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                if(j==0) {    //끝이 0일때 앞에 1만 올 수 있음
                    dp[i][j] = dp[i - 1][1] %mod;
                } else if (j == 9) {   //끝이 9일때 앞에 8만 올 수 있음
                    dp[i][j] = dp[i - 1][8] %mod;
                } else {
                  dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) %mod;
                }
            }
        }
        long result = 0;
        for (int i = 0; i < 10; i++) {
            result+=dp[n][i];
        }
        System.out.println(result %mod);
    }
}