[BOJ 2688] 줄어들지 않아 (Java, DP)

 

 

 

---

문제 링크

https://www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

---

문제 풀이

- 초기 DP배열을 구하는데 시간복잡도 O(64 * 10 * 10) 

- 문제 지문 "어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다."에 따라 00, 01, 02와 같은 형태의 숫자 개수를 찾음 

- DP[2][1] 은 2자리 수이면서 시작이 1인 줄어들지 않는 수를 뜻함

 

초기화 DP[1][i]의 경우 모두 1 (해당 문제에서 0또한 포함) 

	0	1	2	3	4	5	6	7	8	9
DP[1]	1	1	1	1	1	1	1	1	1	1
DP[2]	10	9	8	7	6	5	4	3	2	1

아래와 같이 값이 구해진다

DP[2][0] 의 경우 00 ~ 09 
DP[2][1] 의 경우  11 ~ 19 
DP[2][2] 의 경우  22 ~ 29
..
DP[2][9] 의 경우 99

0~10까지의 합 = N ( N + 1 ) / 2 = 55

---

제출 코드 

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int T, N;

    static long[][] DP;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        T = Integer.parseInt(br.readLine());
        while(T > 0) {
            T -= 1;

            N = Integer.parseInt(br.readLine());
            sb.append(sumValue(N)).append("\n");
        }
    }

    static long sumValue(int n) {
        long result = 0L;
        for(long v : DP[N]) {
            result += v;
        }

        return result;
    }

    static void preProcess() {
        DP = new long[65][10];

        for(int i = 0; i <= 9; i++) DP[1][i] = 1;

        for(int i = 2; i <= 64; i++) {
            for(int j = 0; j <= 9; j++) {
                for(int k = j; k <= 9; k++) {
                    DP[i][j] += DP[i - 1][k];
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        preProcess();
        input();
        System.out.println(sb);
    }
    
}