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

문제

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

---

풀이(18분)

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

public class Main {

    /**
     * 한자리수는 0 1 2 3 4 5 6 7 8 9
     * 두자리수는
     * 00 01 02 03 04 05 06 07 08 09
     * 11 12 13 14 15 16 17 18 19
     * 22 23 24 ... 이런 식
     * 즉 10 *
     */

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

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

        for(int i = 0; i < t; i++){
            int n = Integer.parseInt(br.readLine());
            long[][] arr = new long[n+1][10]; // n+1행에 대해 0~9까지의 자릿수
            for(int j = 0; j < 10; j++){
                arr[1][j] = 1; // 한자릿수 모두 1로 초기화
            }
            for(int j = 2; j <= n; j++){
                long sum = 0;
                for(int k = 9; k >= 0; k--){
                    sum += arr[j-1][k];
                    arr[j][k] = sum;
                }
            }
            long answer = 0;
            for(int j = 0; j < 10; j++){
                answer += arr[n][j];
            }
            System.out.println(answer);
        }
    }
}

---

문제 풀이 전략

 

줄어들지 않는 숫자를 만드는 것이 중요하다.

그 말은 앞자리에 새로운 숫자를 추가할 때마다 이 전 자릿수들에 대한 고려를 할 수 있다는 것이다.

 

예를 들어 생각해 보자.

1. 한자릿수는 0 1 2 3 4 5 6 7 8 9로 반드시 줄어들지 않게 된다.

2. 두 자릿수는 어떻게 될까? 1의 자리가 9라면 반드시 9만 들어올 수 있고, 8이라면 8,9가 되고, 7이라면 7,8,9가 된다.

즉, DP 규칙을 찾아낼 수 있게 된 것이다!

 

최종적으로 자릿수에 따른 배열을 만들어 해결할 수 있다.