백준 동적계획법 - 10844번 : 쉬운 계단 수

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

10844번: 쉬운 계단 수

---

import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		long[][] memo = new long[101][10];
		for(int i=1; i<=n; i++) {
			for(int j=0; j<=9; j++) {
				if(i==1) {
					if(j==0)continue;
					memo[i][j]++;
				}
				else {
					if(j==0) {
						memo[i][j] = memo[i-1][1]%1000000000;
					}
					else if(j==9) {
						memo[i][j] = memo[i-1][8]%1000000000;
					}
					else {
						memo[i][j] = (memo[i-1][j-1]%1000000000)+(memo[i-1][j+1]%1000000000);
					}
				}
				
			}
		}
		long sum = 0;
		for(int i=0; i<10; i++) {
			sum = sum + memo[n][i];
		}
		sum%=1000000000;
		bw.write(sum+"");
		bw.close();
	}
	
}