<Algorithm> 214. 줄어들지않아(BOJ)

1. 2688번 줄어들지않아(BOJ)

   사용 알고리즘 :  DP

• DP 기본적인 문제, 규칙을 찾아서 그걸 코드로 구현할 수 있는지 묻는 문제라는 생각이 들었다.

• 예전에 비슷한 문제를 풀어본 기억이 있어서 금방 풀 수 있었던 것 같다. 

문제에 대한 접근&생각

1. 최대 64자리의 줄어들지 않는 수 -> 완전탐색 불가! -> DP!
2. 규칙 : 11~ 99까지 45가지 ( 1+2~+8+9), 100~999는 165가지 (1+3+~+36+45)
3. 결과적으로 이전의 합의 누적이 된다. (1~9까지 합, 1~8까지합 ~)

코드 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long[][] dp = new long[66][10];
        for(int i = 1; i < 10; i++) {
            dp[1][i] = i;
        }
        /***************************
         * DP를 이용해 이전값이 범위가 
         * 줄어들면서 누적되는 규칙을
         * 적용하여 값을 출력한다.
         ***************************/
        for(int u = 2; u <= 65; u++) {
            for(int i = 1; i < 10; i++) {
                for(int j = 1; j <= i; j++) {
                    dp[u][i] +=dp[u-1][j];
                }
            }
        }
        int n = sc.nextInt();
        while(n-->0) {
            int k = sc.nextInt();
            long res = 10;
            if(k == 1) {
                System.out.println(res);
                continue;
            }
            for(int i = 2; i <= k; i++) {
                res += Arrays.stream(dp[i-1]).sum();
            }
            System.out.println(res);
        }
        
    }
}