백준2688_줄어들지않아

문제

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

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

입력

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

출력

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

 

import java.util.Scanner;
 
public class B2688_줄어들지않아 {
 
    public static int n = 0;
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt(); // 테스트케이스 개수
        for (int i = 0; i < tc; i++) {
            n = sc.nextInt(); // 자리수
 
            long dp[][] = new long[65][65];
            long ans[] = new long[65];
            for (int j = 0; j < 10; j++) {
                dp[0][j] = 1;
            }
            
            ans[0] = 10;
            for (int j = 1; j < n; j++) {
                long sum = 0;
                for (int k = 0; k < 10; k++) {
                    dp[j][k] = dp[j-1][k] + sum;
                    sum += dp[j-1][k];
                }
                ans[j] = 0;
                for (int k = 0; k < 10; k++) {
                    ans[j] += dp[j][k];
                }
            }
 
            System.out.println(ans[n - 1]);
        }
 
    }
 
}
 

 

[알고리즘]

 

거의 내가 짠 게 아니기 때문에 여기엔 그냥 소스 보관용으로 올려둔다.

dp는 아주 쉬운 문제여도 점화식을 세우는 과정이 너무 힘든 것 같다.

이것도 누가 올려둔 코드를 보고 세웠다. 감을 잡으면 좀 괜찮아질 것 같기는 한데... 

dfs/bfs 와는 다르게 dp는 많은 연습이 필요한 것 같다. ㅠㅠ 휴가 기간에는 매일 한번씩 푸는 걸 목표로...!