[BOJ/C++] 오르막 수(11057번)

1. 개요

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

11057번: 오르막 수

1-1. 설명

오르막 수는 수의 자리가 오름차순으로 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성한다. 수는 0으로 시작할 수 있다. 

1-2. 제한 사항

 - 첫 줄에 N이 주어지며, N은 1 이상 1,000 이하

---

2. 구현

2-1. 풀이

DP의 Bottom-up 방법으로 풀었다. 2차원 배열을 두어, 아래의 표처럼 값을 넣었다.

	0	1	2	3	...	6	7	8	9
1	1	2	3	4		7	8	9	10
2	1	3	6	10		28	36	45	55
...	1

점화식은 dp[i][j]에서 j가 0이면, dp[i][j] = 1, 0이 아니면 dp[i][j-1] + dp[i-1][j]가 도출된다. N을 1부터 3까지 나열하여 도출한 결과이다. 

2-2. 코드

#include <iostream>
using namespace std;

constexpr size_t MAX_NUM = 1001;
constexpr size_t DIV_NUM = 10007;

int dp[MAX_NUM][10];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N;
    cin >> N;
    for (int i = 0; i < 10; i++) {
        dp[1][i] = i + 1;
    }
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) dp[i][j] = 1;
            else dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % DIV_NUM;
        }
    }
    cout << dp[N][9];
    return 0;
}