백준-11057번/오르막 수 (java)

 

우선 이차원 배열을 만들어준다.(n+1 ==> 수의 길이, 10 ==> 각 자리에 0부터 9까지의 수가 올때의 경우의 수)

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

 

만약 n이 1인 경우는 0,1,2,3,4,5,6,7,8,9가 있으므로 dp[1][i]를 모두 1로 해준다.

 

점화식 만들기

 

 

ex) i번째 자리에 3이 오는 경우:

i-1번째 수에 3~9까지의 수가 올 수 있다.

 

i번째 자리에 x가 오는 경우:

i-1번째  수에 x~9까지의 수가 오늘 경우의 합!

 

점화식

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

 

 

점화식을 바탕으로 만든 정답 코드

 

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

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