[백준] 2688 줄어들지않아

문제보기

오랜만에 풀어보는 bottom-up 방식의 DP였다. 점화식을 세워서 풀면 된다.
d[i][j] 는 i 번째 수로 끝나는 j 자리 수의 갯수를 뜻한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;

class Main{
	
	static int ip(String s){ return Integer.parseInt(s); };
	static long[][] d;
	
     public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    	int t = ip(br.readLine());
    	d = new long[10][65]; // 끝자리로 가능한 수는 0~9까지 10개, 자릿수는 최대 64자리까지 나온다고 했으므로..
    	
    	for(int i = 0 ; i < 10 ; i++) {
    		d[i][1] = 1; // 초항 설정해주기. i로 끝나는 한자리 수는 하나뿐이다.
    	}

    	for(int len = 2 ; len < 65 ; len++) { // 자릿수 
    		for(int end = 0 ; end < 10 ; end++) { // 끝 숫자 
    			long temp = 0;
    			for(int prev = 0 ; prev <= end ; prev++) { // 끝 숫자보다 작거나 같은 len-1자리 수의 합 구하기
    				temp += d[prev][len-1];
    			}
    			d[end][len] = temp; 
    		}
    	}
    	
    	StringBuilder sb = new StringBuilder();

    	while(t-- >0) {
    		int n = ip(br.readLine());
    		long ans = 0;
		// 모든 끝자리 수에 대하여 n자리 수의 갯수를 합산한다 
    		for(int end = 0 ; end < 10 ; end++) {
    			ans += d[end][n];
    		}

    		sb.append(ans + "\n");
    	}
    	System.out.println(sb);
     }
}