[알고리즘_dp] 백준 11057, 오르막 수

점화식 : d[자리수N][자리수가_N일때_시작하는수] = d[자리수N-1][k] (시작하는 수<=k<=9)

 

package dp;
import java.util.Scanner;

public class backjoon_10844 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[][] d = new int[N+1][10];

        int mod = 10007;

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

        for(int i=2; i<=N; i++){
            for(int j=0; j<=9; j++){
                for(int k=j; k<=9; k++){
                    d[i][j] += d[i-1][k];
                    d[i][j] %= mod;
                }
            }

        }

        long ans = 0;

        for(int i=0; i<=9; i++){
            ans += d[N][i];
        }

        ans %= mod;

        System.out.println(ans);

    }
}

 

---

---

 

생각의 흔적!.!