10844

1. 쉬운 계단 수

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

---

2. 나만의 문제 해결

n = 7 일 때,
xxxxxx3의 계단 수는
xxxxx2, xxxxx4의 계단 수의 합이다.

즉, 총 계단 수는 앞에서 올 수 있는 모든 계단 수의 합이다.

f(n, 0) = f(n-1, 1)
f(n, 1) = f(n-1, 0) + f(n-1, 2)
f(n, 2) = f(n-1, 1) + f(n-1, 3)
f(n, 3) = f(n-1, 2) + f(n-1, 4)
f(n, 4) = f(n-1, 3) + f(n-1, 5)
f(n, 5) = f(n-1, 4) + f(n-1, 6)
f(n, 6) = f(n-1, 5) + f(n-1, 7)
f(n, 7) = f(n-1, 6) + f(n-1, 8)
f(n, 8) = f(n-1, 7) + f(n-1, 9)
f(n, 9) = f(n-1, 8)

---

3. code

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		long[][] sum = new long[n+1][10];
		int mod = 1000000000;
		long result = 0;

		for (int i = 1; i < 10; i++) {
			sum[1][i] = 1;
		}

		for (int i = 2; i <= n; i++) {
			sum[i][0] = sum[i-1][1];
			for (int j = 1; j < 9; j++) {
				sum[i][j] = (sum[i-1][j-1] + sum[i-1][j+1]) % mod;
			}
			sum[i][9] = sum[i-1][8];
		}
		for (int i = 0; i < 10; i++) {
			result = (result + sum[n][i]) % mod;
		}
		System.out.println(result);
	}
}