[백준(baekjoon) 11057] 오르막 수

문제

백준 11057

n이 주어질 때, n개의 자리인 오름차순의 개수를 구하는 문제

• 예시 : 2232, 1234, 4311
• 주의 : 인접한 수가 같아도 된다.

해결

오름차순의 조건이 끝의 자리보다 작거나 같은 수이기 때문에,
끝의 자리가 0..9인 개수를 모두 따져보면 된다. 그 결과는 다음과 같다.

해당 표는 int[][] count = new int[n][10]라는 2차원 배열로 나타낼 수 있다.
count[n][i]는 n번째에 i로 끝나는 수들의 총 개수이고,
count[n][i] = count[n-1][i] + count[n][i-1]라는 규칙을 가지고 있다.

저는 왜 그런지 궁금해하면서 원리를 어떻게든 파악하는 편이라,
여기서 부터 너무 복잡하게 설명해놨으므로 패스하셔도 무방합니다.

그 이유는 다음과 같다.
k로 끝난 수의 경우, 오름차순이 될 수 있는 새로운 끝 수는 k...9이다.
즉, n번째에 새로운 끝 수 i가 나올 수 있는 경우는 n - 1일 때 끝 수가 k <= i인 총 개수가 될 것이다.

n = 2, i = 2이고, k가 n = 1의 모든 수들의 끝 수 일때, 다음과 같다.

그런데 0으로 끝나는 수는 무조건 1이다. i = 1부터 차례대로 시작해보면 count[n][i-1]은 n-1번째의 0...k-1로 끝나는 수들의 합임으로 알 수 있다.
즉, count[n][i]는 **count[n][i-1] + 자기와 같은 수로 끝나는 경우 = count[n-1][i]가 된다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

1. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.
8.        long sum = 0;
9.        for (int su : goTo(n)) sum += su;
10.        System.out.println(sum % 10007);
11.    }
12.
13.    static int[] goTo (int n) {
14.        int[] current = new int[10];
15.        if (n == 1) {
16.            for (int i = 0; i < 10; i++) current[i] = 1;
17.        }else {
18.            int[] before = goTo(n - 1);
19.            current[0] = 1;
20.            for (int i = 1; i < 10; i++) current[i] = (current[i-1] + before[i]) % 10007;
21.        }
22.        return current;
23.    }
24.}

2. Bottom-Up 방식

1.import java.util.*;
2.import java.util.*;
3.
4.public class Main {
5.    public static void main(String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int n = sc.nextInt();
8.
9.        int[] temp = new int[10];
10.        for (int i = 0; i < 10; i++) temp[i] = 1;
11.
12.        for (int j = 1; j < n; j++) {
13.            for (int i = 1; i < 10; i++) {
14.                temp[i] = (temp[i] + temp[i-1]) % 10007;
15.            }
16.        }
17.
18.        long sum = 0;
19.        for (int i = 0; i < 10; i++) {
20.            sum += temp[i];
21.        }
22.        System.out.println(sum % 10007);
23.    }
24.}

결과

1. Top-Down 방식
2. Bottom-Up 방식