[백준/C++] 11057번: 오르막 수

문제

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

---

문제 요약

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다.

 

이 때, 인접한 수가 같아도 오름차순이라고 가정한다.

 

수의 길이 N이 주어졌으 때, 오르막 수의 개수를 출력한다.

+ 수는 0으로 시작할 수 있다.

---

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;

// dp[i][j]: i자리 수 중 j로 끝나는 오르막 수
int dp[1010][10];

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    // 1자리 수일 때 오르막 수의 개수 설정
    for (int i = 0; i < 10; i++) {
        dp[1][i] = 1;
    }
    
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            // dp[i][j] = dp[i - 1][0 ~ j]
            for (int k = 0; k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
            }
            dp[i][j] = dp[i][j] % 10007;
        }
    }

    // 수의 길이가 n인 오르막 수의 개수
    int res = 0;
    for (int i = 0; i < 10; i++) {
        res += dp[n][i];
    }

    cout << res % 10007;
    return 0;
}

---

코드 설명

Bottom - Up 다이나믹 프로그래밍을 이용해 문제를 해결한다.

 

1. dp[i][j]를 수의 길이가 i일 때, j로 끝나는 오르막 수의 개수를 저장하는 DP 테이블로 정의한다.

 

2. 초기 dp[1][j]을 작성한다.

(수의 길이가 1일 때, j로 끝나는 오르막 수의 개수 = 1)

 

3. dp[i][j]는 dp[i - 1][0 ~ j]를 모두 더한 값이다.

 

즉, 수의 길이가 i - 1이고, 0 ~ j로 끝나는 오르막 수 뒤에 j를 붙이면

=> 수의 길이가 i이고, j로 끝나는 오르막 수가 된다.

---

고찰

일반적인 2차원 DP에 한 번 더 반복문을 이용하는 방식이다.

 

실제로 아래처럼 일일이 나열해보며 규칙을 찾았는데, 시간이 조금 걸렸다.

/*
n = 1
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
=> 10

n = 2
00, 01, 02, 03, 04, 05, 06, 07, 08, 09
=> 10
11, 12, 13, 14, 15, 16, 17, 18, 19
=> 9
22, 23, 24, 25, 26, 27, 28, 29
=> 8
33, 34, 35, 36, 37, 38, 39
=> 7
44, 45, 46, 47, 48, 49
=> 6
55, 56, 57, 58, 59
=> 5
66, 67, 68, 69
=> 4
77, 78, 79
=> 3
88, 89
=> 2
99
=> 1
*/