오르막 수

📍 문제 설명

 

💡 접근

쉬운 계단수 문제와 비슷한 문제

i 자리의 숫자가 j라는 숫자로 끝나는 경우의 수를 표현하는 2차원 dp 배열을 사용한다.

dp[2][0] = 1

dp[2][1] = 2

...

dp[2][9] = 10

 

👩‍💻 코드

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

public class Main {
    static int n, m, k, min, max, answer = Integer.MAX_VALUE, mod = 10007;
    static int[][] board;
    static int[][] arr, dp, t, p;
    static boolean[][] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static ArrayList<String> list = new ArrayList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //dp[n][i]은 n 자리의 숫자가 i 라는 숫자로 끝나는 경우의 수
        n = kb.nextInt();
        dp = new int[n+1][10];
        for(int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

        for(int i = 2; i <= n; i++) {
            for(int j = 0; j < 10; j++) {
                for(int k = 0; k <= j; k++) {
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= mod;
                }
            }
        }
        int sum = 0;
        System.out.println(Arrays.deepToString(dp));
        for(int i = 0; i < 10; i++) sum += dp[n][i];
        System.out.println(sum%mod);
    }

    private void solution() {
    }
}