백준 11057번: 오르막 수 [DP] - Java

www.acmicpc.net/problem/11057

11057번: 오르막 수

자리수가 1~3일때를 써보고 규칙을 발견했다.

dp[자리수][j = 0~9으로 시작하는 수 ] += d[자리수-1][ j~9로 시작하는 수]

 

ex) 3자리의 6으로 시작하는 수의 갯수는 2자리의 6~9까지 시작하는 수를 모두 더한 것과 같다.

 

 

* 주의점 : 10007의 나머지로 값을 출력해야한다.

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {

	public static long[][] dp;
	public static void main(String[] args) {
		


		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		dp = new long[n+1][10]; //dp[자리수][0~9로 시작하는 수의 갯수]
		
		//1자리 일때 세팅
		for (int i = 0; i <= 9; i++) {
			dp[1][i] = 1;
		}
		
		//bottom-up계산
		for (int i = 2; i <= n; i++) {
			for (int j = 0; j <= 9; j++) {
				long sum = 0;
				for (int k = j; k <= 9; k++) {
					sum += dp[i-1][k];
				}
				dp[i][j]=sum%10007;
			}
		}
		
		long res = 0;
		for (int i = 0; i <= 9; i++) {
			res += dp[n][i];
		}
		
		System.out.println(res%10007);

	}

}