2688 줄어들지 않아 (Java)

줄어들지 않아

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다.

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

풀이

줄어들지 않는 수를 자릿수대로 확인해보자
1자리 일 경우는 다음과 같다.
끝자리 숫자 줄어들지 않는 수의 갯수
0 -> 1
1 -> 1
.
.
.
9 -> 1

2자리일 경우는 다음과 같다.

끝자리 숫자 줄어들지 않는 수의 갯수
0 -> 1 (00)
1 -> 2 (01,11)
2 -> 3 (02,12,22)
.
.
.
9 -> 10 (09,19,29.....99)
이 결과를 자세히 살펴보면 자릿수를 n 마지막 자리수를 m이라고 할때 dp[n][m] = dp[n-1][0~m까지의 합]임을 알 수 있다.
즉 점화식은 다음과 같다.
// n = 자릿 수, m = 마지막 숫자
dp[n][m] = dp[n][0] + dp[n][1] + .... + dp[n][m]

이를 코드로 구현하면 다음과 같다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long[][] dp = new long[65][10];

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());

            sb.append(find(dp[num])).append("\n");
        }

        System.out.println(sb);
    }

    static long find(long[] arr){
        long ret = 0;
        for(long i : arr){
            ret += i;
        }
        return ret;
    }
}