[10844]쉬운 계단 수

문제

https://www.acmicpc.net/problem/10844

풀이

2차원 배열로 메모이제이션해야 되는 문제였다.

D[N][L]을 N자리수에서 끝자리가 L로 끝나는 수의 계단수의 가지수라고 한다면

N자리 수에서 끝자리가 2로 정해지면, D[N-1][1]과 D[N-1][3]을 구하면 된다.

이를 점화식으로 표현하면

D[N][L] = D[N-1][L-1] + D[N-1][L+1]

import java.util.Scanner;
 
public class Main {
    static int[][] d = new int[101][10];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        for(int i=1;i<=9;i++) d[1][i] = 1;
        //d[1][0] = 0;
        for(int i=2;i<=n;i++) {
            for(int j=0;j<=9;j++) {
                if(j-1>=0) d[i][j] += d[i-1][j-1];
                if(j+1<=9) d[i][j] += d[i-1][j+1];
                d[i][j] %= 1000000000;
            }
        }
 
        long sum = 0;
        for(int i=0;i<=9;i++) {
            sum += d[n][i];
        }
        System.out.println(sum%1000000000);
        scan.close();
    }
}