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

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

2688번: 줄어들지 않아

풀이

사용한 알고리즘 : DP

 

풀이전략

1자리 d[1]	2자리 0으로 시작	2자리 1로 시작	2자리 2로 시작
d[1][0] = 1	d[2][0] = 00	d[2][1] = 11	d[2][2] = 22
d[1][1] = 1	d[2][0] = 01	d[2][1] = 12	d[2][2] = 23
d[1][2] = 1	d[2][0] = 02	d[2][1] = 13	d[2][2] = 24
d[1][3] = 1	d[2][0] = 03	d[2][1] = 14	d[2][2] = 25
d[1][4] = 1	d[2][0] = 04	d[2][1] = 15	d[2][2] = 26
d[1][5] = 1	d[2][0] = 05	d[2][1] = 16	d[2][2] = 27
d[1][6] = 1	d[2][0] = 06	d[2][1] = 17	d[2][2] = 28
d[1][7] = 1	d[2][0] = 07	d[2][1] = 18	d[2][2] = 29
d[1][8] = 1	d[2][0] = 08	d[2][1] = 19
d[1][9] = 1	d[2][0] = 09

위 표를 보면 d[i][j]=d[i-1][j]+d[i-1][j+1]+ ... d[i-1][9]  이라는 규칙을 발견할 수 있다.

따라서 d[1]부터 d[n]까지 바텀업 형식으로 값을 저장하여 올라가면 효율적으로 문제를 풀이할 수 있다.

 

 

제출코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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

        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;++i) {
            long d[][] = new long[65][10];
            Arrays.fill(d[1],1);
            int n = Integer.parseInt(br.readLine());
            for (int j = 2; j <=n; ++j) {
                for (int k = 0; k < 10; ++k) {
                    for (int a = k; a < 10; ++a) {
                        d[j][k] += d[j - 1][a];
                    }
                }
            }
            long result=0;
            for(int j=0;j<10;++j){
                result+=d[n][j];
            }
            System.out.println(result);
        }
    }
}