[백준] 11057 오르막 수 - DP JAVA

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

11057번: 오르막 수

코드설명

DP 문제입니다.

 

문제로직입니다.

처음에 한자리수는 모두 1 로 초기화합니다. 한자리수는 1개의 수만 가지고 있습니다.

이 문제에서는 00000 도 하나의 숫자라고 보고 있으므로 0 도 같이 넣습니다.

dp[1][0] = 1;
dp[1][1] = 1;
dp[1][2] = 1;
dp[1][3] = 1;
dp[1][4] = 1;
dp[1][5] = 1;
dp[1][6] = 1;
dp[1][7] = 1;
dp[1][8] = 1;
dp[1][9] = 1;

 

 

예시와 함꼐 설명해보겠습니다.

만약 DP[3][5]의 값이 몇이여야할까요? 답은 15 입니다.

이유는 DP[3][5] 는 DP[2][0] + DP[2][1] + DP[2][2] + DP[2][3] + DP[2][4] + DP[2][5] 입니다.

이유는 3자리수인데 마지막이 5로 끝나는 숫자가 오름차순이 되는 방법은 2자리 숫자의 끝자리가 0 1 2 3 4 5 일경우에 연속해서 나타낼 수 있습니다.

 

만약 3이 주어졌을떄  DP배열의 값은 아래와 같습니다.

N : 2
answer : 220

DP 
 1 1 1 1 1 1 1 1 1 1
 1 2 3 4 5 6 7 8 9 10
 1 3 6 10 15 21 28 36 45 55
 
위와 같이 출력됩니다.

 

핵심로직입니다.

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

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	
	public static int N;
	public static long[][] dp;
	public static long answer;
	public static int MOD = 10007;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	dp = new long[N+1][10];
    	dp[1][0] = 1;
    	dp[1][1] = 1;
    	dp[1][2] = 1;
    	dp[1][3] = 1;
    	dp[1][4] = 1;
    	dp[1][5] = 1;
    	dp[1][6] = 1;
    	dp[1][7] = 1;
    	dp[1][8] = 1;
    	dp[1][9] = 1;
    	
    	for(int i=2; i<N+1;i++) {
    		for(int j=0; j<=9;j++) {
    				for(int k=0;k<=j;k++) {
    					dp[i][j] += ( dp[i-1][k] ) % MOD;	
    				}
    		}
    	}
    	for(int i=1; i<N+1;i++) {
    		for(int j=0; j<=9;j++) {
    			System.out.print(" "+dp[i][j]);
    		}
    		System.out.println();
    	}
    	
    	for(int i=0; i<=9;i++) {
    		answer += dp[N][i];
    	}
    	
    	System.out.println(answer);
    	
    }
}