[백준] 2688: 줄어들지 않아 - JAVA

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

 

풀이

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

 

예를 들어, 1234, 0011, 2223 과 같은 숫자는 줄어들지 않는 수이다.

 

이 문제에서는 0000과 같이 숫자의 앞에 0이 있어도 숫자로 인정이 되는 문제였다.

 

dp를 이용해 해결했다.

 

이차원 배열을 만드는데, long[][] dp = new long[max + 1][10]; 으로 테스트케이스의 최댓값까지 1씩 늘려가면서, 0~9까지 10개의 숫자를 확인할 수 있게 하였다.

 

예를 들어, dp[2][8]이 의미하는 바는 2자리 줄어들지 않는 수 중 8로 끝나는 수들의 개수를 의미한다.

 

1자리 숫자들을 모두 1로 초기화를 해주고 시작했다.

 

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

 

초기화 후 2부터 탐색하여, 해당 자리수의 j로 끝나는 숫자의 개수는

 

자리수 하나 적은 수들 중 끝나는 값이 j보다 작은 수들의 개수를 더해주었다.

 

---

 

메모리: 13972KB
시간: 116ms
언어: Java 11

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        int[] testCase = new int[t];
        int max = 0;
        for (int i = 0; i < t; i++) {
            testCase[i] = Integer.parseInt(br.readLine());
            max = Math.max(testCase[i], max);
        }

        long[][] dp = new long[max + 1][10];
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

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

        long[] result = new long[max + 1];
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            if (result[testCase[i]] == 0) {
                for (int j = 0; j < 10; j++) {
                    result[testCase[i]] += dp[testCase[i]][j];
                }
            }
            sb.append(result[testCase[i]]).append("\n");
        }

        System.out.println(sb);
    }

}