[백준 11057 java 자바] 오르막 수 (DP-이차원배열)

[Silver I] 오르막 수 - 11057

문제 링크

성능 요약

메모리: 11544 KB, 시간: 80 ms

분류

다이나믹 프로그래밍(dp)

문제 설명

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

---

풀이

자리수 + 올 수 있는 수로 점화식을 세우는게 중요하다.
세번째 자리에 올 수 있는 오르막 개수는 dp[3][9]~dp[3][0]의 총 합인데,
dp[3][4]는 4xx (dp[2][5] + dp[2][6] ... + dp[2][9]의 조합에 앞에 4를 붙인 경우) 이다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[][] dp;
    static int mod = 10007;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1][10];
        for (int i = 0; i <= 9; i++) {
            dp[1][i] = 1;
        }

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = j; k >= 0; k--) {//오름차순이라 왼쪽에서 오른쪽으로 숫자가 큰 경우만 따져야 한다.
                    dp[i][j] += dp[i - 1][k] % mod;//dp에 저장할 때 마다 mod로 나누는것 잊지 않기.
                }
            }
        }

        int result = 0;
            for (int j = 0; j <= 9; j++) {
                result += dp[N][j] % mod;
            }
        System.out.println(result%mod);
    }
}