백준 2688번: 줄어들지 않아

문제 설명

• https://www.acmicpc.net/problem/2688
• 뒷자리 숫자가 앞자리 숫자보다 크거나 같은 숫자를 줄어들지 않는 숫자라고 합니다. 줄어들지 않는 숫자는 0으로 시작할 수 있습니다. n자리의 줄어들지 않는 숫자가 몇개인지 구해야 합니다.

접근법

• n-1자리에서 만들 수 있는 줄어들지 않는 숫자의 개수로 n자리에서 만들 수 있는 줄어들지 않는 숫자의 개수를 계산할 수 있습니다.

• 줄어들지 않는 숫자를 판단할 때는 마지막 숫자가 가장 중요합니다.

  • 어떤 숫자의 마지막이 8로 끝났다면 그 다음에는 8또는9가 와야 줄어들지 않는 숫자입니다.
  • 어떤 숫자의 마지막이 0으로 끝났다면 그 다음에는 0~9가 와야 줄어들지 않는 숫자입니다.
  • 5자리의 줄어들지 않는 숫자 중 마지막이 3으로 끝나는 경우의 수는
    • 4자리의 줄어들지 않는 숫자 중 마지막이 0으로 끝나는 경우의 수
      + 4자리의 줄어들지 않는 숫자 중 마지막이 1로 끝나는 경우의 수
      + 4자리의 줄어들지 않는 숫자 중 마지막이 2로 끝나는 경우의 수
      + 4자리의 줄어들지 않는 숫자 중 마지막이 3으로 끝나는 경우의 수
      이 됩니다.

• 즉, dp[i][j] = dp[i][9] + dp[i][8] + ... + dp[i][j]가 됩니다.

정답

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		long[][] dp = new long[10][65];
		for (int i = 0; i < 10; i++) {
			dp[i][0] = 1;			
		}
		// 숫자 계산
		for (int j = 1; j <= 64; j++) { // j자리 숫자
			for (int i = 0; i < 10; i++) { // 끝자리가 i로 끝남
				for (int k = 0; k < 10-i; k++) {
					dp[i][j] += dp[9-k][j-1];
				}
			}
		}
		// 정답 출력
        // n자리 숫자의 경우의 수는 n+1번째 숫자의 0으로 끝나는 경우의 수와 동일합니다.
		for (int t = 0; t < T; t++) {
			int idx = Integer.parseInt(br.readLine());
			System.out.println(dp[0][idx]);
		}
		
	}

}