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

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

11057번: 오르막 수

 

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

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());

        final int MOD = 10007;

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

       for(int i=0; i<10; i++){
           dp[1][i] = 1;
       }
       for(int i=1; i<=n; i++){
           dp[i][0] = 1;
       }

       for(int i=2; i<=n; i++){
           for(int j=1; j<10; j++){
               dp[i][j] = dp[i][j-1] + dp[i-1][j] % MOD;
           }
       }
       int answer = 0;
        for(int i=0; i<10; i++){
            answer += dp[n][i];
        }
        System.out.println(answer % MOD);
    }
}

 

앞서 풀었던 쉬운 계단 수랑 문제가 비슷해서 쉽게 생각해낼 수 있었다.

 

dp[i][j] = d[i][j-1] + dp[i-1][j] 
(i자리수의 숫자 중 j로 끝나는 수) = (i자리 수 중 j-1로 끝나는 수) + (i-1자리 수 중 j로 끝나는 수)

 

위의 점화식은 dp[i][j] = dp[i-1][0~j] 의 합에서 도출된 결과이다.

 

예를 들어, 3자리 수 중 4로 끝나는 수 dp[3][4] 는

2자리수 0으로 끝나는 수 + 2자리 수 1로 끝나는 수 + 2자리수 2로 끝나는 수 + 2자리 수 3으로 끝나는 수 + 2자리 수 4로 끝나는 수

이다.

(dp[i][j]= dp[i-1][0]부터 dp[i-1][j] 까지의 합)

 

 

그런데 dp[i][j-1]이 (dp[i-1][0]부터 dp[i-1][j-1]의 합)과 같으므로 

dp[i][j] = d[i][j-1] + dp[i-1][j] 

이렇게 한줄로 표현할 수 있는 것이다. 

 

 

 

표로 보면 이해가 더 쉽다.

	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	10	15	21	28	36	45	55

 

 

 

 

아래는 3중 for문을 돌며 dp[i-1][0]부터 dp[i-1][j-1]의 합을 구하는 코드이다. 

 

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

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());

        final int MOD = 10007;

        int[][] dp = new int[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<10; j++){
               for(int k=0; k<=j; k++){
                   dp[i][j] += dp[i-1][k];
                   dp[i][j] %= MOD;
               }
           }
       }
       int answer = 0;
        for(int i=0; i<10; i++){
            answer += dp[n][i];
        }
        System.out.println(answer % MOD);
    }
}