[백준-11057번] 오르막 수 풀이 - Java

🚀 문제

 

 

🚀 접근 방법

DP문제이다.!

백준 10844번 쉬운 계단수와 비슷한 풀이 방법이다.

끝자리가 0이면 0~9

1이면 1~9

....

9이면 9만 올 수 있는 것을 이용한다.

0	1	2	3	4	5	6	7	8	9
0~9	1~9	2~9	3~9	4~9	5~9	6~9	7~9	8~9	9

 

🚀 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        final int MOD = 10007;

        int[][] dp = new int [n+1][10];

        for(int i=0; i<=9; i++){
            dp[1][i] = 1;
        }

        for(int i=2; i<=n; i++){
            for(int j=0; j<=9; j++){
                for(int k=j; k<=9; k++){
                    dp[i][k] += (dp[i-1][j]%MOD);
                }
            }
        }

        bw.write(Long.toString((Arrays.stream(dp[n]).sum()%MOD)));
        bw.flush();
        bw.close();
        br.close();
    }
}