[백준] 11057 오르막 수 - Dynamic Programming / Java

• 문제 링크

11057번: 오르막 수

 

• 풀이 과정

2차원 dp배열을 생성, 이는 dp[자릿수][0 ~ 9] 를 나타낸다.

 

먼저 i = 0 ~ 9, dp[0][i] = 1 로 초기화한다.

그리고 규칙성을 찾기 위하여 1 ~ 3 의 자릿수의 값의 따라 오르막 수의 개수를 나타내면 아래와 같다.

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

n번째 자릿수의 0 ~ 9 범위의 각 숫자(j)에서 만들 수 있는 오르막 수의 개수는,

이전 자릿수(n - 1) 에서 j ~ 9 까지 구해진 오르막 수의 개수의 합이다.

 

예시로 dp[2][6] = 10 이며, 이는 dp[1][6] ~ dp[1][9] 의 값을 모두 합한 값, 4 + 3+ 2+ 1 = 10 과 같다.

 

이를 토대로 i = 1 ~ n, j = 0 ~ 9, k = j ~ 9 의 범위의 3중 for 문에 dp[i][j] += dp[i - 1][k] 를 적용시켜

각각의 오르막 수의 개수를 나타내고 % 10007 을 수행한다.

 

이 후 각 자릿수의 오르막 수의 개수 dp[n][0] 에 % 10007 을 수행한 값을 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n + 1][10];

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

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

        bw.write(dp[n][0] % 10007 + "\n");
        bw.flush();
    }

}