[B10844][쉬운 계단 수][java]

 

풀이

 

길이가 N인 인접한 모든자리가 1인 수

n = 1
1 2 3 4 5 6 7 8 9

n = 2
10
21
12 32
23 43
34 54
45 65
56 76
67 87
78 98
89
10 / 12 21 / 23 32 / 34 43 / 45 54 / 56 65 / 67 76 / 78 87 / 89 98

n = 3
210
101 121 321
212 232 432
123 323 343 543
234 434 454 654
345 545 565 765
…
567 767 787 987
678 878 898
789 989

끝 자리가
0 = 1
1 = 0, 2
2 = 1, 3
…
8 = 7, 9
9 = 8

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

// 키 포인트는 이전 n의 끝 자리 수에 따라 개수는 일정하다는 것
// 끝 자리가 0일 땐 다음 수로 1 만 올 수 있고, 마찬가지로 9일 땐 8 만 올 수 있다.
// 2 일 땐 1, 3 이 올 수 있고, 2~8 은 동일하다.
public class Main {
    static long mod = 1_000_000_000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] dp = new long[n + 1][10];

        for (int i = 1; i < 10; i++) dp[1][i] = 1;

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < 10; j++) {
                if (j == 0) dp[i][0] = dp[i - 1][1] % mod;
                else if (j == 9) dp[i][9] = dp[i - 1][8] % mod;
                else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % mod;
            }
        }

        System.out.println(Arrays.stream(dp[n]).sum() % mod);
    }
}