줄어들지 않아 - 백준 2688

문제 링크

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

 

문제 풀이

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때라고 한다. 그렇다면 숫자를 구성할 때 특정 자리 k 이후의 숫자는 특정 자리 k의 수 이상을 만족하면 된다. 이때 숫자는 leading zero여도 만족하므로 0부터 9까지의 숫자 중에 줄어들지 않는 조건을 만족하는 순열을 구하면 되는 문제이다.

어떻게 되는지 확인해보자

1 자리 수일 때

1 자리 수인 경우 앞에 어떤 숫자도 올 수 없기 때문에 0,1,2,3,4,5,6,7,8,9 가 가능하며 10가지 수가 존재한다.

2 자리 수일 때

2 자리 수인 경우는 1 자리 수에서 확장해볼 수 있다.

• 첫 번째 자리 수가 0인 경우
  • 두 번째 자리 수는 0~9까지 숫자가 가능하다.
• 첫 번째 자리 수가 1인 경우
  • 두 번째 자리 수는 1~9까지 숫자가 가능하다.
• 첫 번째 자리 수가 2인 경우
  • 두 번째 자리 수는 2~9까지 숫자가 가능하다.
• 첫 번째 자리 수가 3인 경우
  • 두 번째 자리 수는 3~9까지 숫자가 가능하다.

이미 눈치채신 분들도 있겠지만 n번째 자리에 가능한 숫자의 갯수는 이전 자리 수부터 9까지 숫자가 올 수 있다는 것을 알 수 있다.

이전 값을 기반으로 같은 동작이 반복된다면 다이나믹 프로그래밍의 메모이제이션 기법으로 문제를 해결할 수 있다.

풀이 코드

파악한 규칙대로 작성한 코드

import java.util.Arrays;
import java.util.Scanner;

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int numberOfTestCases = scanner.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numberOfTestCases; i++) {
            int n = scanner.nextInt();
            long[][] dp = new long[n + 1][10];
            for (int j = 0; j < 10; j++) {
                dp[1][j] = 1;
            }
            for (int j = 2; j <=n; j++) {
                for (int k = 0; k < 10; k++) {
                    for (int l = k; l < 10; l++) {
                        dp[j][k] += dp[j-1][l];
                    }
                }
            }
            long answer = Arrays.stream(dp[n]).sum();
            sb.append(answer+"\\n");
        }
        System.out.println(sb);
        scanner.close();
    }

}

좀 더 dynamic programming 답게 수정한 코드

import java.util.Scanner;

public class Main3 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int numberOfTestCases = scanner.nextInt();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numberOfTestCases; i++) {
            int n = scanner.nextInt();
            long[][] dp = new long[n + 1][11];
            
            // 0의 자리일 때 초기화
            for (int j = 0; j <= 10; j++) {
                dp[0][j] = 1;
            }
            // 1부터 n번째 자리 수까지 경우의 수 누적
            for (int j = 1; j <= n; j++) {
		            // j번째 자리 수일 때 숫자별로 가능한 경우의 수를 누적
                for (int k = 1; k <= 10; k++) {
                    dp[j][k] = dp[j][k - 1] + dp[j - 1][k];
                }
            }
            // 마지막 열에 j 번째 행의 값이 모두 누적되므로 
            // n번째 행의 10 번째 열의 값이 정답
            sb.append(dp[n][10]).append("\\n");
        }
        System.out.println(sb);
        scanner.close();
    }
}

좀 더 dp답게 푼 코드가 근소하게 시간이 덜 걸리는 것을 볼 수 있다.