[BOJ] 백준 [11057] 오르막 수 JAVA

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

11057번: 오르막 수

문제

풀이

앞 자리 기준으로 자리 수가 늘어날때마다 추가로 들어간다고 생각하면 된다.

점화식은 다음과 같다 => dp[i][j] += dp[i-1][k];

i : 자릿수

j : 현재 자릿수의 0~9 

k : 이전 자릿수의 0~9 

 

그런데 이전 자릿수의 모든 수가 들어가는 것이 아닌 k<=j 까지 일때만 누적 합을 구해주면 된다.

 

import java.util.*;
import java.io.*;
 
public class Main{
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n+1][10];
 
        Arrays.fill(dp[1],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] %= 10007;
                }
            }
        }
        System.out.println(Arrays.stream(dp[n]).sum()%10007);
    }
}