[Java] 11057번: 오르막 수 Silver 1

문제 링크

문제집 바로 다음 순서의 Silver 1 문제가 이건 아닌데, 15번 문제랑 비슷한 거 같아서 가져왔다.

N = 1 일 때는, 0 ~ 9 라서 10이다.
N = 2 일 때는, 00, 01 ~ 11, 02 ~ 22, ... , 09 ~ 99 라서 1 + 2 + 3 + ... + 10 = 55다.

N = 1 에서 N = 2를 어떻게 만들었는 지를 생각해보면, 0 앞에는 0 1개, 1 앞에는 0과 1 2 개, ... 9앞에는 0 ~ 9 10개가 올 수 있다.

이런 식으로 N = 3을 만든다고 생각해보면, N = 2에서 만들어진 각각의 케이스에 또 앞에 숫자를 추가하는 경우를 생각해보면 된다!

앞자리가 0인 수는 1개 만들어졌으니 마찬가지로 0을 하나 추가할 수 있다.

앞자리가 1인 수는 01 과 11로 2개 만들어졌는데 마찬가지로 각각 0 과 0 ~ 1로 1개와 2개를 추가할 수 있다. 그러면 총 (1+2)개를 만들 수 있다.

이런 식으로 앞에 추가할 수 있는 개수의 곱만큼 경우의 수가 생긴다.

그렇다면 15번 문제 10844번: 쉬운 계단 수 처럼 배열로 관리하면 된다!!

그리고 각 배열마다 앞에 추가할 수 있는 수의 개수만큼 계속 곱해서 값을 증가시키면 된다.

정답

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // N 입력 받기
        int N = Integer.parseInt(br.readLine());

        // 배열 입력 받기
        int[][] dp = new int[N][10];
        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }

        // dp
        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][j] + dp[i - 1][k]) % 10007;
            }
        }

        // 출력
        int ans = 0;
        for (int i = 0; i < 10; i++) {
            ans = (ans + dp[N - 1][i]) % 10007;
        }
        System.out.println(ans);
    }
}