[백준] 11057번 : 오르막 수 (JAVA)

인간몽쉘김통통·2023년 12월 19일

다이나믹 프로그래밍 백준 알고리즘

백준

목록 보기

37/92

문제

이해

오르막 수는 수의 각 자릿수가 오름차순을 이루는 수를 의미한다. 단, 인접수가 같아도 오름차순으로 친다.

예를 들어, 1234, 1134, 6689는 오르막 수이고 4251, 5274, 8764는 오르막 수가 아니다.

자릿수 N이 주어질 때, 오르막 수의 개수를 출력하면 된다.

접근

탐색에 관한 문제이다. 가능한 오르막 수의 개수를 세면 되는데 처음에는 자릿수에 수를 집어넣고 그 다음 자릿수를 재귀적으로 결정하는 DFS로 풀이하였다.

하지만 N의 최댓값은 1000이므로 DFS로 치면 depth가 1000이 되도록 조사하여야 하기 때문에 이는 적절하지 않아 보인다.

따라서, N의 따른 오르막 수의 규칙을 찾아보기로 한다. (DFS처럼 세는 것은 불가능하므로 계산을 통해 세기 위해서)

1 -> 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 10
2 -> 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55
3 -> 55 + 45 + 36 + 28 + 21 + 15 + 10 + 6 + 3 + 1 = 220
4 -> 220 + 165 + ...

가장 앞쪽에 있는 자릿수에 따라 가능한 경우를 기준으로 세운 식이다.

예를 들어 N = 2 인 경우에는

0 -> 00, 01, 02, ... , 09 = 10
1 -> 11, 12, ... , 19 = 9

으로 식을 구성할 수 있다.

그렇다면 N에 따라 규칙성을 찾아보자.

N=3 일때 앞자리가 0인 경우는 N=2일 때의 전체 오르막 수와 같다.

그 이유는 앞자리가 0이면 뒤의 2자리는 어떤 수든 올 수 있기 때문에 N=2일 때의 오르막 수로 결정된다.

앞자리가 1인 경우에는 어떻게 될까? 이는 단순하게 둘째자리부터 구성되는 모든 경우 N=2의 경우에서 앞자리가 0인 경우를 빼면 된다.

왜냐하면, 앞자리가 1이면 둘째자리에는 0이 오지 못하기 때문이다.

앞자리가 2인 경우에는 어떻게 될까? 1일때와 마찬가지로 N=2의 전체 경우에서 둘째 자리가 0과 1인 경우를 빼면 된다.

이쯤이면 규칙이 있다는 것을 파악할 수 있다.

ascending_cnt[i][j] (i는 자릿수, j는 앞자리 수 : 0 ~ 9) 으로 점화식을 표현하면 다음과 같다.

ascending_cnt[i][j] = ascending_cnt[i-1]의 합 - ascending_cnt[i-1][j-1]

위 점화식으로 코드를 작성해보았다.

코드

package java_baekjoon;

import java.util.*;
import java.io.*;

public class prob11057 {
    static int N;
    static long[][] ascending_cnt;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        ascending_cnt = new long[1001][11];
        for(int i=0;i<10;i++){
            ascending_cnt[1][i] = 1;
        }
        ascending_cnt[1][10] = 10;

        for(int i=2;i<=N;i++){
            ascending_cnt[i][10] = ascending_cnt[i][0] = ascending_cnt[i-1][10];
            for(int j=1;j<10;j++){
                ascending_cnt[i][j] = ascending_cnt[i][j-1] - ascending_cnt[i-1][j-1] + 10007;
                ascending_cnt[i][j] %= 10007; 
                ascending_cnt[i][10] += ascending_cnt[i][j];
            }
            ascending_cnt[i][10] %= 10007;
        }

        System.out.println(ascending_cnt[N][10]);
    }
}

ascending_cnt[i]의 자릿수의 합을 중복하여 계산하지 않기 위해 ascending[i][10]에는 해당 자릿수에서의 총 합을 저장한다. 이는 다음 자릿수에 값을 계산할 때 사용된다.

그리고 자릿수가 특정값 이상 넘어가면 int 형의 범위를 넘어선다. 그래서 문제에서는 10007의 나머지 계산으로 값을 조절한다.

하지만 점화식을 보면 알 수 있듯이 점화식은 뺄셈 형식으로 구성되기 때문에 이전 과정에서 나머지 연산을 하면 값의 대소 관계가 바뀔 수도 있다. (실제로는 ascending_cnt[i][j-1]가 ascending_cnt[i-1][j-1] 보다 항상 크지만 나머지 연산 과정에서 관계가 바뀔수도 있다.)

따라서, 점화식의 값이 항상 양수가 나올 수 있도록 bias 값을 더해주었다. (10007)

나머지 연산이 포함된 연산에서 이처럼 bias값을 더해줄 수 있는 이유는 나머지 연산의 분배법칙 때문이다.

10007 % 10007 = 0 이기 때문에 bias를 더해도 전체 식의 값에는 영향을 미치지 못한다.