[PS] 백준 10844번 쉬운 계단 수 - DP

 

문제

10844번: 쉬운 계단 수

 

풀이

dp[자릿수길이][마지막자릿수]로 이차원 배열을 사용하여 푼다. 이 풀이를 참고하였다.

0~9까지의 숫자를 사용할 수 있으나 0이 첫번째 자리에 오면 안된다.

따라서 길이가 1인 dp[1][1~9]의 값은 순서대로 1,2,3,4,5,6,7,8,9 로 경우의 수가 1개씩 밖에 없다.

길이가 1인 계단수의 총 개수는 9개가 된다.

 

1~9까지의 숫자의 경우, 계단 수 규칙에 따라 옆자리에 -1, +1인 수가 올 수 있다. (경우의 수가 2)

 

위 필기에서 나열된 dp[2][ ], dp[3][ ]의 경우의 수를 보면 알 수 있듯이

규칙성에 따라 도출되는 점화식 dp[n] = dp[n-1][마지막자릿수-1] + dp[n-1][마지막자릿수+1]을 사용한다.

마지막 자릿수가 0인 경우에는 +1, 9인 경우에는 -1 의 수만 올 수 있으므로(경우의 수가 1) 예외처리를 해준다.

주의할 점: 값이 크므로 long 타입을 사용한다.

 

코드

import java.util.Scanner;

public class Main {

    final static long mod = 1000000000;

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

        //자릿수가 2일 때부터  ~ N일 때까지 탐색
        for(int i=2; i<=N; i++) {

            for(int last=0; last<10; last++) {

                //마지막 자릿수가 0이면 +1만 가능
                if(last == 0) {
                    dp[i][0] = dp[i-1][1] % mod;
                }
                //마지막 자릿수가 9이면 -1만 가능
                else if(last == 9) {
                    dp[i][9] = dp[i-1][8] % mod;
                }

                //그 외 +1, -1 두가지 경우 가능
                else {
                    dp[i][last] = (dp[i-1][last-1] + dp[i-1][last+1]) % mod;
                }
            }
        }

        long result = 0;

        for(int i=0; i<10; i++) {
            result += dp[N][i];//자릿수가 N인 경우의 수 모두 더한다
        }

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