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

[문제]

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

2688번: 줄어들지 않아

---

[문제풀이 전]

 

플레티넘급의 dp문제를 풀어본적은 없지만 항상 문제를 잘 읽어 제한조건과 요구하는 정답을 보고, 규칙을 빠르게 파악하여 dp테이블을 만들 수 있도록 하는게 중요하다고 생각이 든다. 답을 찾아 보면 쉬운데, 그 풀이를 얻는 과정이 조금 어렵다고 생각하기 때문에 시간이 좀 걸리는 것 같다. 

 

---

[문제풀이]

 

문제에서 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 요구한다. 줄어들지 않는 수는 주어진대로 각 자리 수 보다 그 왼쪽 자리 수가 작거나 같을 때 인데, 0000, 0001, 0111 , 0234 등 이렇게 이루어진다. 그래서 손으로 계산하기 쉬운 한자리수부터 직접 계산을 해서 규칙을 발견을 해보면 됩니다.

 

우선 한 자리수를 만들어보면 0, 1, 2, 3, 4 ... 9 로 모두 10개로 구성이 된다.

두 자리수는 00, 01, 02, ... 11, 12, 13 ..... 55, 56, 57 ..... 88, 89, 99 로 이루어지는데 이전 자리수와의 규칙성을 발견할 수 있습니다.

 

0로 시작하는 두 자리수는 00,01,02... 09 로 10개    ---> 이전 자리수의 0 ~ 9 까지의 개수의 합 

1로 시작하는 두 자리수는 11,12,13... 19로 총 9개      ---> 이전 자리수의 1 ~ 9 까지의 개수의 합

2로 시작하는 두 자리수는 22,23,24... 29로 총 8개   ---> 이전 자리수의 2 ~ 9 까지의 개수의 합

.

.

.

9로 시작하는 두 자리수는 99로 총 1개  ---> 이전 자리수의  9 ~ 9 까지의 개수의 합

 

dp[i][j] = dp[i-1][j] + dp[i-1][j+1] ...  + dp[i-1][8] + dp[i-1][9] 라는 식을 구할 수 있습니다. [ i = 자리수(1 ~ 64) ,  j = 숫자( 0 ~ 9)]

 

한자리수는 모두 1로 구성되어있어 미리 초기화를 시켜주며, 이 문제는 참고로 테스트 케이스가 있는데 매번 테스트 케이스마다 이 값들을 구할 필요없이 미리 dp테이블을 완성시켜, 테스트케이스안에서는 단순 원하는 자리수의 값만 구하여 출력하게 만들면 된다.

그리고 더하는 값이 너무 커져 오버플로우가 일어날 수 있으니 테이블은 int 가 아닌 long을 써주면 된다.

 

 

---

[소스코드] 

 

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        long[][] d = new long[65][10]; //자리수 max 64 , 숫자 1~9
        

        for (int i = 0; i <= 9; i++) {
            d[1][i] = 1;
        }

        //미리 dp테이블 완성하기, while 불필요한 작업X
        for (int k = 2; k <= 64; k++) {
            for (int i = 0; i <= 9; i++) {
                for (int j = i; j <= 9; j++) {
                    d[k][i] += d[k - 1][j];
                }
            }
        }

        int t = Integer.parseInt(br.readLine());


        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine());
            long ans = 0;

            for (int i = 0; i <= 9; i++) {
                ans += d[n][i];
            }

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

        System.out.println(sb);
    }
}