[Java] 백준 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		long cnt = 0;
		Scanner s = new Scanner(System.in);
		int N = s.nextInt();
		
		long dp[][] = new long [N+1][10+1];
		
		//한 자리 수 초기화
		for(int i = 0; i < 10; i++) {
			dp[1][i]=1;
		}
		
		for(int i=2; i <= N; i++) {
			dp[i][0] = dp[i - 1][1];
			for(int j=1; j <10; j++) {
				dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
			}
		}
		
		for(int i=1;i<10;i++) {
			cnt += dp[N][i];
			
		}
		
		System.out.print(cnt%1000000000);
	}
}