[JAVA] 백준 10844번_쉬운 계단 수

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

10844번: 쉬운 계단 수

---

DP문제라고 해서 규칙성 찾는 것에 너무 매몰되지 말 것. 전반적인 흐름을 보자

• 길이가 N-1인 계단수의 개수가 An-1이라면, An = 2*An-1 - (N-1에서 1, 8의 개수)
  • 9 - (9*2-1 = 17) - (17 * 2 - 2 = 32) ...
• 그 전 자릿수가 k였다면, 다음 자릿수로는 k+1, k-1이 가능하다. 
  • 전 자릿수가 1, 8인 경우 0, 9 가 발생 된다. 
  • 1, 8의 개수는 결국 0, 2, 7, 9의 개수와 동일함 -> 얘만 볼게 아니라 전체적으로 따지는게 편함
• dp[N-1][K] : 길이가 N인 계단 수에서 K가 나오는 횟수 => dp[N][K-1] , dp[N][K+1] 에 기여

dp를 long형으로 선언해줘야 함(나중에 sum 구할 때) , %10^9 잊지 말 것!

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

public class Main_10844 {
    static long[][] dp;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        dp = new long[N + 1][10];
        for (int i = 1; i < 10; i++) {
            dp[1][i] = 1;
        }
        if(N != 1) {
            for (int i = 1; i < N; i++) {
                dp[i + 1][0] = dp[i][1];
                dp[i + 1][9] = dp[i][8];
                for (int j = 1; j < 9; j++) {
                    dp[i + 1][j] = (dp[i][j - 1] + dp[i][j + 1])%1000000000;
                }
            }
        }
        System.out.println(Arrays.stream(dp[N]).sum() % 1000000000);
    }
}