알고리즘 풀이 - 백준 11057(오르막 수, DP)

 

관련글

 

Dynamic Programming 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

 

이 문제는 N 자리의 숫자가 주어졌을 때, 오르막 수의 개수를 구하는 문제이다.

 

※ 오르막 수란?

오름차순으로 숫자가 이루어진 경우를 의미한다. 예를 들어 112334는 오르막수 이지만 1121은 아니다.
즉, N의 자리에서 1의 자리로 이동하며 숫자가 점점 커지거나 이전의 숫자와 같은 경우에만 해당한다.

숫자가 0으로 시작할 수도 있다!

 

 

2. 풀이

 

N자리의 숫자가 있고 좌측부터 1번째, 1번째 ~, N번째의 자리수라고 생각해보자.(N자리 이므로 index 기준)

N자리의 숫자에서 1~N까지 1번째를 제외한 자리수에서 모두 이전 위치의 숫자에 영향을 받게 된다.

예를 들어 N = 3이라고 한다면 1번째, 2번째, 3번째 자리수에 대해 생각해보자.

 

① 1번째에서는 0~9까지 모든 숫자가 올 수 있다. 따라서 경우의 수는 10가지이다.
② 2번째에서는 0~9까지 모든 숫자가 올 수 있으나 1번째의 숫자에 영향을 받는다.
  → 1번째가 0이라면, 0~9의 10가지, 1번째가 1이라면 1~9의 9가지..
③ 3번째에서는 0~9까지 모든 숫자가 올 수 있으나 2번째의 숫자에 영향을 받는다.
  → 2번째가 0이라면, 0~9의 10가지, 2번째가 1라면 1~9의 9가지..

 

여기서 ①은 N=1인 상태의 경우의 수일 것이다. ②는  N=2인 상태이며 ③은 N=3인 상태이다.

이 부분에서 우리는 문제를 작게 나눌 수 있고 이전의 경우의 수가 반복적으로 나타나고 그대로 사용할 수 있으니 DP로 해결할 수 있을 것이라는 실마리를 찾을 수 있다.

 

DP라면 State를 우선 알아야 한다. State는 즉, 변수이므로 우리는 숫자의 길이인 N과 1~N번째의 0~9까지의 숫자가 올 수 있으니 어떤 숫자가 오는지를 M이라고 한다면 2개의 State가 있음을 이해할 수 있다.

즉, State를 저장할 배열은 DP[][]의 2차원 배열로 구성해야 할 것이다.

 

DP로 해결하기로 했다면 State의 정의를 우선 다시 세워보자. 
정의 : DP[N][M] = N번째 자리수의 숫자 M이 올 수 있는 오르막 수의 경우의 수

즉, DP[3][3] 이라면 123과 같은 경우가 해당할 수 있다. 3번째에 3이 올 수 있는 경우이기 때문이다. 이를 이용해 DP로 반복문 또는 재귀를 통해 해결할 수 있다.

 

그러면 점화식과 기저 상태를 알아보자. 점화식은 아래와 같을 것이다.

점화식 : $DP[N][M] =DP[N][M] = \sum_{i=0}^{M} DP[N-1][i]$

 

기저 상태는 N=1일 때이다. DP[1][i]은 모두 1로 초기화한다.
기저 상태 : $DP[1][i] = 1$

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

 

1) Bottom-up 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static final int MOD = 10007;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        dp = new int[1001][10];
        
        // n=1일 때는 1로 모두 초기화.
        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] %= MOD;
                }
            }
        }
        
        int result = 0;
        for(int i=0; i <= 9; i++){
            result += dp[n][i];
            result %= MOD;
        }
        bw.write(String.valueOf(result));
        
        bw.flush();
        br.close();
    }
}

 

2) Top-Down 방식

import java.io.*;

public class Main{
    static int[][] dp;
    static final int MOD = 10007;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        dp = new int[1001][10];
        int n = Integer.parseInt(br.readLine());
        
        int result = 0;
        for(int i=0; i <= 9; i++){
            result += topDown(n, i);
            result %= MOD;
        }
        
        bw.write(String.valueOf(result));
        bw.flush();
        br.close();
    }
    
    // Top-down 방식
    public static int topDown(int n, int i){
        if(n == 1) return dp[n][i] = 1; // 기저 상태
        if(dp[n][i] > 0) return dp[n][i]; // 기존의 값이 있는 경우
        
        for(int k=0; k <= i; k++){
            dp[n][i] += topDown(n-1, k);
            dp[n][i] %= MOD;
        }
        
        return dp[n][i];
    }
}

 

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.