[BOJ - JAVA] 11057 - 오르막수(DP)

# 주소

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

11057번: 오르막 수

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] dp = new int[n+1][10];
        for(int i = 0; i < 10; i++){
            dp[0][i] = 1;
        }
        for(int i = 1; i < n+1; i++){
            for(int j = 0; j < 10; j++){
                for(int k = j; k < 10; k++){
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }
        
        System.out.println(dp[n][0] % 10007);
    }
}

점화식 문제입니다. 제가 점화식이 많이 약해서 푸는데 다른 분들의 아이디어를 얻었습니다.

점화식은 특히 2차원 배열을 이용해서 푸는 것이 가장 어렵다고 느껴집니다. 이것 역시 표로 이해하는 것이 빠릅니다.

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
2	10	9	8	7	6	5	4	3	2
3	55	45	36	28	21	15	10	6	3
4	220	165	120	84	56	35	20	10	4

자 보시면 옆에 행 하나가 잘렸는데 이렇게만 봐도 확연히 눈에 잘 보입니다.

그러니까 dp[4][1] = dp[3][1] 부터 dp[3][10]까지 다 더한 값입니다.

그러므로 dp[i][1]의 자리에는 바로 위에 있는 행의 값을 전부 다 더한 값입니다. 

또한 가장 마지막에 있는 열의 크기는 1인데 열이 잘려서 나오진 않는다는 점 양해부탁드립니다..

 

한편 그 외의 값들은 단순한 뺄셈을 통하여 유추할 수 있습니다.

즉 dp[3][2]로 예를 든다면 dp[3][1] - dp[2][2]를 통해 dp[3][2]가 무엇인지 짐작할 수 있습니다. 따라서 모든 dp의 값들은 바로 윗 행부터 제 10열까지 값을 전부 더한 것이 됩니다.

그러므로 n의 오르막 수 값은 dp[n+1][0]의 값이므로 출력해주시면 됩니다.