위 문제는 백준 사이트의 알고리즘 11057 문제에 관한 설명입니다.

오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

소스코드

package day0905;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ11057 {
    public static void main(String args[])throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] DP = new int[N+1][10];
        for (int i=0; i<=9; i++) {
            DP[1][i] = 1;
        }
        for (int i=2; i<=N; i++) {
            for (int j=0; j<=9; j++) {
                for (int k=0; k<=j; k++) {
                    DP[i][j] += DP[i-1][k];
                    DP[i][j] %= 10007;
                }
            }
        }
       int ans = 0;
        for (int i=0; i<10; i++) {
            ans += DP[N][i];
        }
        ans %= 10007;
        System.out.println(ans);
    }
}

해당 문제는 DP문제였습니다.

어떤 점화식을 사용해야할까 생각해보았습니다.

하나씩 살펴봅시다.

D[N][]은 길이가 N인 오르막 수의 개수를 저장할 곳입니다.

그리고 DP[N][M]은 M으로 끝나는 오르막의 갯수들을 담을 곳입니다.

길이가 1인경우를 살펴봅시다.

1 1 1
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1

길이가 1인 경우는 위의 모습과 같이 어차피 길이가 1이라면 오르막길은 본인이 있는 곳 하나입니다.

따라서 길이가 1인경우는 모든 DP값을 1로 설정합니다.

모든 경우를 다 더하면 answer은 0 ~ 9 = 10이 됩니다.

이번엔 다른 숫자 한개를 생각해봅시다.

길이가 2인 경우도 생각해봅시다.

앞자리가 0인 경우 0,1,2,3,4,5,6,7,8,9 10개

앞자리가 1인 경우 1,2,3,4,5,6,7,8,9 9개

앞자리가 2인 경우 2,3,4,5,6,7,8,9 8개

…

앞자리가 9인 경우 9 1개

10+9+8+….+1 = 55개

길이가 3인 경우는?

앞자리 0, 둘째자리 0인 경우 셋째자리 0,1,2,3,4,5,6,7,8,9 10개

앞자리 0, 둘째자리 1인 경우 셋째자리 1,2,3,4,5,6,7,8,9 9개

….

앞자리 0, 둘째자리 9인 경우 셋째자리 1개

10+9+8+ …+ 1 = 55개

앞자리 1, 둘째자리 1인 경우 셋째자리 1,2,3,4,5,6,7,8,9 9개

앞자리 1, 둘째자리 2인 경우 셋째자리 2,3,4,5,6,7,8,9 8개

…

앞자리 1, 둘째자리 9인 경우 셋째자리 1개

9+8+7+6+…+1 = 45개

….

55+45+36+28+21+…+6+3+1 = 220개

슬슬 감이 올 겁니다.

점화식은 따라서 D[N] = D[N][0] + D[N][1] + D[N][2] + … + D[N][9]로 나올 수 있겠네요!

중간중간 10007로 나누어주면서 값을 확인합시다.

오르막 수