백준 11057 / 오르막 수

문제

풀이

설명

수의 자리가 오름차순을 이루는 수를 오르막 수라고 하는데
다만 같은 수가 이어져도 오르막 수가 될 수 있다.

D[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수
D[1][i] = 1
D[i][j] = D[i-1][k] (0<=k<=j)

코드

import java.util.Scanner;

public class Num11057 {
	public static long mod = 10007;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
        int n = sc.nextInt();
        long[][] d = new long[n+1][10];
        
        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=0; k<=j; k++) {
                    d[i][j] += d[i-1][k];
                    d[i][j] %= mod;
                }
            }
        }
        
        long ans = 0;
        
        for (int i=0; i<10; i++) {
            ans += d[n][i];
        }
        ans %= mod;
        System.out.println(ans);
		
	}

}

코드설명

참고 :
출처 : https://www.acmicpc.net/problem/11057