[백준] 11057번 오르막 수 - Java, 자바

난이도

실버 1

문제

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

풀이

1. 테이블 정의하기

D[i] = 수의 길이 i일 때, 오르막 수의 개수

2. 점화식 찾기

N = 1 한자리 수일 경우, 0~9경우 10가지
N = 2 두자리 수일 경우,

0로 시작할 때, 10가지
1로 시작할 때, 10가지
2로 시작할 때, 9가지
3로 시작할 때, 8가지
...
9로 시작할 때, 1가지
총 55가지

즉, 0~9까지의 각 숫자(j)에서 만들 수 있는 오르막수는 이전 자릿수 N-1에서의 j부터 마지막 9까지의 합이다.

3. 초기값 정하기

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

코드

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

// 11057번 오르막 수
public class boj_4_11057 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        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 + 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]);

    }
}