[백준] 11057번 오르막 수

📖 문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

✍ 입력

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

📄 출력

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

✅ 코드

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
  
public class Main {  
    static final int DIVIDE_VALUE = 10_007;  
  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int N = Integer.parseInt(br.readLine());  
        int[][] arr = new int[N+1][10];  
  
        // (1) 길이가 1인 경우 초기화  
        for(int i=0; i<10; i++) {  
            arr[1][i] = 1;  
        }  
  
        // (2) DP 점화식 적용  
        for(int i=2; i<=N; i++) {  
            for(int j=0; j<10; j++) {  
                if(j == 0) {  
                    arr[i][j] = 1;  
                } else {  
                    arr[i][j] = (arr[i-1][j] + arr[i][j-1]) % DIVIDE_VALUE;  
                }  
            }  
        }  
  
        // (3) 결과 합산  
        int result = 0;  
        for(int i=0; i<10; i++) {  
            result = (result +arr[N][i]) % DIVIDE_VALUE;  
        }  
  
        System.out.println(result);  
    }  
}

🧩 코드풀이

해당 문제는 bottom-up 방식의 DP 알고리즘을 이용해서 문제를 풀었습니다.

1️⃣ dp[i][j]의 정의

• dp[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수

2️⃣ 점화식 도출

• 오르막 수의 특성상, 현재 숫자 j는 이전 숫자보다 작아질 수 없다.
• 따라서, 길이가 i이고 끝자리가 j인 경우, 이전 자릿수 i-1에서 j 이하의 숫자가 와야 한다.
• 이를 점화식으로 정리하면: arr[i][j] = arr[i-1][j] + arr[i][j-1]
  • dp[i-1][j] → 이전 자리(i-1)에서 마지막 숫자가 j인 경우
  • dp[i][j-1] → 같은 자리(i)에서 0 ~ j-1까지의 숫자를 더한 값

3️⃣ 초기값 설정

• arr[i][0]의 값들은 1 이므로 전부 1을 입력한다.
• 길이가 1인 경우, 모든 숫자는 1개씩 존재하므로 dp[1][i]의 값들은 1로 초기화 한다.

4️⃣ 결과값 계산

• dp[N][0] ~ dp[N][9]까지 모두 합산한 후 10,007로 나눈 나머지를 출력한다.