백준 11057번 : 오르막 수 자바

 

🧫 문제 분석

 

✔️ 출처

오르막 수 실버 1

 

📖 문제

 

깊이 별로 나누되 0~10까지 에 대해서 동적프로그래밍을 한다.

 

중요한 점

수는 0으로 시작할 수 있다는 것이다.

 

 

현재 깊이의 각 수는 이전 깊이의 현재 수부터 9까지의 개수 합을 더하면 된다. 

 

 

수 \ 깊이	1	2	3
0	1	깊이 1의 0~9까지 : 10	깊이 2의 0~9 까지 : 55
1	1	깊이 1의 1~9까지 : 9	깊이 2의 1~9까지 : 45
2	1	깊이 1의 2~9까지 : 8	깊이 2의 2~9까지 : 36

 

잘 모르겠다면 노드로 직접 그려보면 바로 알기 쉽다.

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

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

        Arrays.fill(dp[1], 1);

        for (int i = 2; i <= n; i++) {

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

                dp[i][j] = sum;
            }
        }

        int sum  = 0;
        for (int i : dp[n]) {
            sum += i;
            sum %= 10007;

        }

        bw.write(sum + "");
        bw.flush();
        bw.close();
    }
}

 

 

 

❗ 오답노트 / 필요한 지식