[백준 10844번] 쉬운 계단 수

문제 링크: 10844번 쉬운 계단 수

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

 

가장 마지막 자리인 mem[1]부터 시작해서 가장 첫 자리인 mem[n]까지 숫자를 붙여나가면서, mem[i]에는 가능한 경우의 수를 저장한다. n=1일 때를 제외하고는 mem[1][digit]에는, 아직 아무것도 정해지지 않은 상태이므로 반드시 1이 들어가야 한다.

 

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static long[][] mem;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		long answer;
		if (n == 1) {
			answer = 9;
		} else {
			/*
			 * mem[1]이 가장 마지막 자리(가장 작은 값의 자리)
			 * mem[n]이 가장 첫 자리(가장 큰 값의 자리)
			 */
			mem = new long[101][10];
			Arrays.fill(mem[1], 1);

			for (int row = 2; row <= n; row++) {
				for (int col = 0; col <= 9; col++) {
					if (col == 0) {
						mem[row][col] = mem[row-1][1];
					} else if (col == 9) {
						mem[row][col] = mem[row-1][8];
					} else {
						mem[row][col] = (long)((mem[row-1][col-1] + mem[row-1][col+1]) % 1e9);
					}
				}
			}
			mem[n][0] = 0;

			long sum = 0;
			for (int i = 0; i <= 9; i++) {
				sum += mem[n][i];
			}
			answer = sum;
		}

		System.out.println((long)(answer%1e9));

		sc.close();
	}
}