[백준 알고리즘] Q11057 오르막수 - 동적프로그래밍, 모듈러 분배법칙

1. Java 구현

            
package Q11057;

import java.util.Scanner;

public class Main {
    /* 오르막수
     *    url : https://www.acmicpc.net/problem/11057 */
    public static void main(String[] args) {
        int n = new Scanner(System.in).nextInt();

        /* D(n)(0~9) = D(n-1)(0) + 2*D(n-1)(1) + 3*D(n-1)(2) … + 9*D(n-1)(8) + 10*D(n-1)(9) */
        /* D(n)(0) = D(n-1)(0~9) = D(n-1)(0~9)
           D(n)(1) = D(n-1)(0~9) - D(n-1)(0) = D(n-1)(1~9)
           D(n)(2) = D(n-1)(0~9) - (D(n-1)(0) + D(n-1)(1)) = D(n-1)(2~9)
           D(n)(x) = D(n-1)(x~9)
        */


        System.out.println(getResultBy2Maxtrix(n));
    }

    public static int getResultBy1Maxtrix(int n) {
        int[] prev = new int[10];
        int[] now = new int[10];

        for (int i = 0; i < 10; i++) {
            prev[i] = 1;
            now[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                now[j] = 0;
            }

            for (int j = 0; j < 10; j++) {
                for (int k = j; k < 10; k++) {
                    now[j] = (prev[k] % 10007 + now[j] % 10007) % 10007;
                }
            }

            for (int j = 0; j < 10; j++) {
                prev[j] = now[j];
            }
        }

        int sum = 0;
        for (int i = 0; i < 10; i++) {
            sum = (now[i] % 10007 + sum % 10007) % 10007;
        }

        return sum;
    }

    public static int getResultBy2Maxtrix(int n) {
        int[][] arr = new int[n][10];

        for(int i = 0; i < arr[0].length; i++) {
            arr[0][i] = 1;
        }

        for(int i = 1; i < arr.length; i++) {
            for(int j = 0; j < arr[0].length; j++) {
                arr[i][0] = (arr[i][0] % 10007 + arr[i - 1][j] % 10007) % 10007;
            }
            for(int j = 1; j < arr[i].length; j++) {
                arr[i][j] = (arr[i][j - 1] % 10007 - arr[i - 1][j - 1] % 10007) % 10007;
            }
        }
        int sum = 0;
        for (int i = 0; i < 10; i++) {
            sum = (arr[n - 1][i] % 10007 + sum % 10007) % 10007;
        }

        return sum;
    }
}

2. 코드설명

 오르막수 문제를 풀기 위해서는 동적프로그래밍을 사용해야 한다. 이 문제를 풀기위해서는 세 가지 접근이 필요하다. 

 첫번째는 점화식 두번째는 메모리제이션 그리고 작은수부터 시작해서 큰 수로 점진적으로 늘리는 방식, 세번째는 모듈러의 분배법칙이다.

 먼저, 규칙을 찾아보자!

           D(n)(0) = D(n-1)(0~9) = D(n-1)(0~9)

           D(n)(1) = D(n-1)(0~9) - D(n-1)(0) = D(n-1)(1~9)

           D(n)(2) = D(n-1)(0~9) - (D(n-1)(0) + D(n-1)(1)) = D(n-1)(2~9)

 D(2)(1)에 의미는, 2자리의 숫자이고, 첫째짜리가 1로 시작하는 모든 수의 수를 의미한다. (예 : 12, 13, 14, 15, ...19, 10(오르막수가 아니다))

 D(2)(1)은 D(1)(1) ~ D(1)(9) 까지의 합과 같다. 왜냐면, 십의자리는 1로 고정하였고, 일의자리는 1보다 크거나 같은 숫자들이 모두 올 수 있다.

 그리고 그 수의 집합들이 D(1)(1)~ D(1)(9) 이다. 결국은 이것을 정리하면 아래와 같은 점화식이 나온다.

            D(n)(x) = D(n-1)(x~9)

 점화식을 구했다면, 이 결과들을 작은수 1부터 시작해서 n 까지 점진적으 늘리면서 배열에 저장하여 메모리제이션을 한다. 

 마지막은 모듈러의 분배법칙을 활용해야 한다. 문제를 보면, 결과값으 10007로 나눈 나머지를 출력하라고 한다. 

D(n)(7) = (D(n-1)(7) + D(n-1)(8) + D(n-1)(9)) % 10007 (x)

D(n)(7) = (D(n-1)(7) % 10007 + D(n-1)(8) % 10007 + D(n-1)(9) % 10007) % 10007 (O)

 이 세가지 방식을 활용해서, 1차배열을 활용한 풀이 방법, 2차 배열을 활용한 풀이 방법을 활용해봤다.

 결국은 같은 방식이다. 1차원 배열은 코드의 가독성이 좋다는 장점은 가지고 있지만, 3중 for문을 활용한다. 아름답지 못하다!

 2차원 배열은 2차 배열을 사용하지만, 1차원 배열보다는 이해가 조금되지 않는다. 그러나 알고리즘은 가독성 << 시간복잡도이니 두번째 방식이 좋다!

3. Pain Point

 처음 문제를 풀었을 때는 1차원배열을 사용했다. 그리고 통과했다. 하지만, for문이 너무 많아, 시간복잡도가 다소 떨어지는 단점이 있다는 것을 생각하고,

 리팩토링을 했다. 그리고 2차원배열로 개선했다. 1차원배열로 먼저 구현했기 때문에 가능했던 것 같다. 규칙성을 찾고, 모듈러의 분배법칙을 모두 알아야만 

 풀 수 있는 문제 였다. 모듈러의 법칙을 간단하게 정리했다.

         (A + B) % C = (A % C + B % C) % C

         (A - B) % C = (A % C - B % C) % C

         (A * B) % C = (A % C * B % C) % C