백준 10844 / 쉬운 계단 수

문제

풀이

설명

D[N][L] = 길이가 N인 계단수, 마지막수 L
마지막 수와 그 앞의 수가 서로 1씩 차이난다는 것을 생각해보면
D[N-1][L-1]
D[N-1][L+1] 로 표기할 수 있다는 것을 알 수 있다.
다만 L의 경우 0~9 까지이므로 앞의 자리가 0이나 9일때 생기는 경우를 예외처리 해주어야 한다. ( 0보다 작은 수 이거나 10이 올 수 없다.)

코드

import java.util.Scanner;

public class Num10844 {
	public static long mod = 1000000000L;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        long[][] d = new long[n+1][10];
        
        for (int i=1; i<=9; i++) {
            d[1][i] = 1;
        }
        for (int i=2; i<=n; i++) {
            for (int j=0; j<=9; j++) {
                d[i][j] = 0;
                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] %= mod;
            }
        }
        long ans = 0;
        for (int i=0; i<=9; i++) {
            ans += d[n][i];
        }
        ans %= mod;
        System.out.println(ans);
	}
}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/10844