[백준/DP] 11057번 오르막 수 (JAVA)

문제

---

풀이

dp[i][j]: i자리 수의 마지막 숫자가 j일 때의 오르막 수의 개수

i-1 길이의 오르막 수의 맨 뒤에 숫자 j를 추가해가는 방식으로 dp[i][j] 배열을 채워나간다. 이 때, countAddable()은 upperBound 이하의 숫자를 마지막 숫자로 갖는 i-1 길이의 오르막 수의 개수를 구한다.

최종 결과로는 dp[n][0]부터 dp[n][9]까지의 합을 구하면 정답이다.

코드

import java.io.*;

public class Main {

    private static final int MAXIMUM = 1000;
    private static final int MOD = 10007;
    private static final int NUMBERS = 10;

    private static int n;
    private static int[][] dp = new int[MAXIMUM + 1][NUMBERS];

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

        n = Integer.parseInt(br.readLine());
        dp();
        bw.append(String.valueOf(sum(dp[n])));

        br.close();
        bw.close();
    }

    private static void dp() {
        for (int i = 0; i < NUMBERS; i++) dp[1][i] = 1;
        for (int i = 2; i <= n; i++)
            for (int j = 0; j < NUMBERS; j++)
                dp[i][j] = countAddable(dp[i - 1], j) % MOD;
    }

    private static int countAddable(int[] arr, int upperBound) {
        int count = 0;
        for (int i = 0; i <= upperBound; i++) count = (count + arr[i]) % MOD;
        return count;
    }

    private static int sum(int[] arr) {
        int sum = 0;
        for (int val : arr) sum = (sum + val) % MOD;
        return sum;
    }
}