---
id: "imported/blog/history/boj/boj-11057"
title: "BOJ 11057 (오르막 수)"
description: "간단한 DP 연습 문제. 오르막 수는 n번째 자리에 올 수 있는 수가 n - 1번째 자리에 올 수 있는 수로 정해진다."
kind: "record"
published: "2023-04-29T00:00:00.000Z"
tags: ["PS","BOJ","DP"]
url: "https://www.readiz.com/blog/history/boj/boj-11057/"
markdownUrl: "https://www.readiz.com/blog/history/boj/boj-11057/index.md"
---

# BOJ 11057 (오르막 수)

- 문제 제목: 오르막 수
- 문제 링크: <https://www.acmicpc.net/problem/11057>

간단한 DP 연습 문제. 오르막 수는 n번째 자리에 올 수 있는 수가 n - 1번째 자리에 올 수 있는 수로 정해진다.

k라는 수가 n번째 자리에 올 수 있는 경우의 수는 n - 1번째 자리에서 0 \~ k까지 올 수 있는 수의 합이 된다.

```
DP[k][n] = DP[k][n-1] + DP[k-1][n-1] + ... DP[0][n-1]
```

경우의 수를 셀 때에는 0번째 위치의 경우의 수를 1로 초기화해서 풀어야 함에 유의.

```cpp
#include <bits/stdc++.h>
using namespace std;

int DP[10][1001];
int main() {
    int N;
    scanf("%d", &N);

    for(int i = 0; i < 10; ++i) {
        DP[i][0] = 1;
    }

    for(int n = 1; n <= N; ++n) {
        for(int K = 0; K < 10; ++K) { // n번째 수가 K일 때 수 세기
            int& T = DP[K][n];
            for(int k = 0; k <= K; ++k) {
                T += DP[k][n - 1];
            }
            T %= 10007;
        }
    }

    printf("%d\n", DP[9][N]);
    return 0;
}
```