[JAVA] 백준 다이나믹 프로그래밍 연습문제 - BOJ 10844

n자리 수 중 각 자리 숫자가 연속하는 수인 계단수의 갯수를 출력하기

 

- d[n+1][10]짜리 배열을 생성하여 메모이제이션

- d[i][j]: i자리수의 수 이면서, 가장 끝자리(일의 자리) 숫자가 j인 계단수의 갯수

 

- n=1일때, 예외처리로 d[1][1]~d[1][9]에 모두 1을 저장함

- i자리 수이면서 j로 끝나는 계단수는, i-1자리 수이면서 j의 연속하는 수인 j-1, j+1으로 끝나는 계단수의 합과 같다.

- 즉, d[i][j]=d[i-1][j-1]+d[i-1][j+1]이다.

- j가 0일 때, 9일 때는 각각 1과 8밖에 연속하는 수가 없으므로 예외처리해준다.

 

import java.util.Scanner;

public class BOJ10844 {
    static final long mob=1000000000L;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt();
        long answer=0;
        int [][]d=new int[n+1][10];

        for(int i=1;i<=n;i++){
            for(int j=0;j<=9;j++) {
                if (i == 1) {
                    d[i][j] = 1;
                }
                else if(j==0){
                    d[i][j] = d[i - 1][j + 1];
                }
                else if(j==9){
                    d[i][j] = d[i - 1][j - 1];
                }
                else {
                    d[i][j] = d[i - 1][j - 1] + d[i - 1][j + 1];
                }
                d[i][j]%=mob;
            }
        }
        for(int i=1;i<=9;i++){
            answer+=d[n][i];
        }
        System.out.println(answer%mob);
    }
}