[backjoon_11057] 오르막 수 (Java)

문제링크

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

11057번: 오르막 수

문제설명

문제

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

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

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

입력

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

출력

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

제한사항

제한시간	메모리제한
1초	256MB

*출처 : https://www.acmicpc.net

문제풀이

다이나믹 프로그래밍을 사용하면 오르막수를 쉽게 해결할 수 있다.

우선, $D(n)$을 정의하여보면, "N자리의 오르막 수"라고 할 수 있다.

이 때 오르막수는 오름차순으로 수가 있어야하기 때문에, 맨 끝의 자리의 수가 가장 중요하다. 맨 끝에 올 수 있는 수의 값은 0부터 9이다.

$a_1$	$a_2$	$a_3$	$a_4$	...	$a_n-3$	$a_n-2$	$a_n-1$	$a_n$
N-1개								1개

총 n개의 자리에 $a_x$의 값이 있다고 하면 맨 끝 $a_n$에 올 수 있는 수가 0부터 9라는 의미이다. 마지막 자리에 어떤 수가 오느냐에 따라 값을 처리해 주도록 구현하기 위해 점화식을 $D(n,i)$로 표현하도록 하겠다.(맨 마지막 수가 i인 경우의 수)

 

이 때 오름차순을 만족하기 위해서 $D(n-1,j)$로 표현할 때 j는 $0 \leq j \leq i$라는 범위를 갖게 된다. 

따라서 최종적으로 구현되는 점화식은 아래와 같다.

$D(n,i) = \sum D(n,j)$ (j는 0부터 i까지의 값)

 

위를 그대로 코드로 구현하여보자.

long count = 0L;
for (int i = 0; i <= last; i++) {
    count += dp(num - 1, i) % 10007;
}

last가 위 점화식에서 i 이다. 재귀로 $D(num-1,j)$를 처리해주는 것을 알 수 있다.

 

최종적으로 재귀식이 return되는 경우는 num이 1인 경우 즉 마지막의 숫자가 정해진 경우 1을 return하여주면 된다.

if(num == 1)
    return 1;

최종적으로 DP를 위한 재귀함수를 보자.

public static long dp(int num, int last) {
    if(num == 1)
        return 1;
    if(dp[num][last] != 0)
        return dp[num][last];

    long count = 0L;
    for (int i = 0; i <= last; i++) {
        count += dp(num - 1, i) % 10007;
    }
    return dp[num][last]  = count % 10007;
}

불러진 재귀함수는 num을 1 내리고 0~마지막수까지 값을 부르는 것을 알 수 있다.

 

for(int i = 0; i < 10; i++){
    sum += dp(num,i);
}

정답을 얻기위해서는 $\sum$ D(n,i) i는 0부터 9까지까지의 합을 구하여 보여주면 된다.

구현코드

import java.util.Scanner;

public class Main {
    static long[][] dp = new long[1001][10];

    public static void main(String[] args) {
        int num = new Scanner(System.in).nextInt();
        int sum = 0;
        for(int i = 0; i < 10; i++){
            sum += dp(num,i);
        }
        System.out.println(sum%10007);
    }

    public static long dp(int num, int last) {
        if(num == 1)
            return 1;
        if(dp[num][last] != 0)
            return dp[num][last];

        long count = 0L;
        for (int i = 0; i <= last; i++) {
            count += dp(num - 1, i) % 10007;
        }
        return dp[num][last]  = count % 10007;
    }
}

 

시간복잡도

모든 문제의 수 : N

문제를 처리하는데 걸리는 시간 : L(last)

따리서 $O(N*L)$이 된다.