[BOJ] 2688번: 줄어들지 않아

 

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

2688번: 줄어들지 않아

 

문제

 

입력

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다.(1 <= n <= 64)

 

출력

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

 

난이도

실버 1

 

Sol

① arr[i][j]에서 i는 해당 수의 자릿수, j는 해당 수의 첫 번째 숫자
② 숫자의 앞에 0이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 수 -> arr[1]0 = 1, arr[1]1 = 1, ...
③ arr[i][j] = arr[i-1][j] + arr[i-1][j+1] + ... + arr[i-1][9]
④ arr[i] (줄어들지 않는 i자리의 수) = arr[i][0] + arr[i][1] + arr[i][2] + ... + arr[i][9]

 

public class B2688_줄어들지않아 {
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        long[][] arr = new long[65][10]; // 1 <= n <= 64, 0~9로 시작하는 숫자

        for(int i=0; i<=9; i++){
            arr[1][i] = 1;
        } // 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수

        for(int i=2; i<=64; i++){
            for(int j=0; j<=9; j++){
                for(int k=j; k<=9; k++){
                    //System.out.println("k = " + k);
                    arr[i][j] += arr[i-1][k];
                    //System.out.println("arr[" + i + "][" + j + "] = " + arr[i][j]);
                }
                // ex) arr[2][3] = arr[1][3] + arr[1][4] + arr[1][5] + arr[1][6] + arr[1][7] + arr[1][8] + arr[1][9]
            }
        }

        int T = sc.nextInt();

        StringBuilder sb = new StringBuilder();

        for(int i=0; i<T; i++){
            int n = sc.nextInt();
            // input
            long ans = 0; // int로 하지 않게 주의할 것!!!!!!!!!!!!

            for(int j=0; j<=9 ; j++){
                ans += arr[n][j]; // arr[n] = arr[n][0] + arr[n][1] + ... + arr[n][9]
            }
            sb.append(ans + "\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

😅

⚠ n을 입력받을 때마다 n자리 수의 개수를 새로 계산하려고 함
-> n이 최대 64이기 때문에 시간 초과가 날 것을 우려해 엎었다

⚠ ans를 int형으로 선언했더니 계속 BOJ에서 틀림
-> long으로 수정 후 성공