[BOJ] 백준 [10844] 쉬운계단수JAVA

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

10844번: 쉬운 계단 수

📝문제

📝풀이

DP 를 활용한 문제이다.
우선 1~9 까지는 한자리 수 니깐 1 이다.

여기서 2번째 자리수는 다음과 같은 상황이 나온다.
0 + ?
1 + ?
2 + ?
3 + ?
4 + ? 
...
9 + ?
여기서 ? 에 올 숫자는 이전 숫자보다 +1 또는 -1 이다.

그런데, 예외가 있다.
만약 9 가 나왔다면 다음은 무조건 8만 나와야 한다. ( 98 )
그리고 0 이라면 이전은 다음건 1만 나와야 한다. 예를들어 10 ? 이 경우엔 다음수는 1만 가능 => 101
그럼 끝자리 경우 자체가 결정자가 될수 있다는 말이고 , 주어진 n 에 대해서도 결정자가 되어야 하니
점화식은 dp[자리수][0~9] 로 식을 세울 수 있다.
 => dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

0과 9일때 예외를 제외하고 bottom-up 방식 점화식

import java.io.*;
import java.util.*;
import static java.util.Arrays.stream;

public class Main {

    static int limit = 1000000000;
    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];

        Arrays.fill(dp[1],1);
        dp[1][0]=0;

        for(int i=2; i<=n; i++){
            for(int j=0; j<10; j++){

                long next = switch (j){ // 숫자 + j
                    case 0->dp[i-1][1]; // 0 일경우 다음은 1만 와야됨
                    case 9->dp[i-1][8]; // 9 일경우 다음은 8만 와야됨
                    default -> dp[i-1][j-1]+dp[i-1][j+1] % limit;
                };
                dp[i][j] = next;
            }
        }
        long result = stream(dp[n])
                .reduce((sum, e) -> (sum + e) % limit)
                .getAsLong();
        System.out.println(result);

    }
}