[BOJ] 오르막 수(11057)

[백준(BOJ)] 오르막 수(11057) C++

문제 : BOJ_11057번 오르막 수

문제 설명

DP

DP로 해결할 수 있는 오르막 수입니다.

1부터 1,000의 수 중 하나인 N이 주어지면, N 자리로 이루어진 오르막 수의 개수를 구하는 문제입니다.

여기서 오르막 수란, 가장 큰 자릿수부터 가장 작은 자릿수가 오름차순으로 올라가야 하는데, 이 문제에선 수가 같아도 오름차순으로 인정해 줍니다.

또 특이한 점은 수가 0으로 시작할 수 있습니다.

---

Solution

저는 2차원 dp 배열을 만들어 문제를 해결했습니다.

dp[수의 길이][가장 큰 자릿수의 수] -> 만족하는 수의 오르막 수의 개수

우선 N이 1인 경우를 생각해봅시다.

문제의 조건이 '수는 0으로 시작할 수 있다.' 임으로, 0,1,2,3 ... 7,8,9 => 10개가 됩니다.

앞선 2차원 배열의 조건에 맞추면 dp[1][0]=1 , dp[1][1]=1 , ... dp[1][9]=1 이 할당됩니다.

이렇게 한 자릿수의 오르막 수에 모두 1을 할당해 주고, 자릿수가 올라간다면 구하고자 하는 수의 길이 -1의 dp를 봐주고 더 해주면 됩니다.

예를 들어, 수의 길이가 3이고 가장 큰 자리수가 5인 오르막 수의 개수를 구하려고 합니다.

그렇다면, 인접한 수가 같아도 오름차순이기 때문에,

dp[3][5] = dp[3-1][5] + dp[3-1][6] + dp[3-1][7] + dp[3-1][8] + dp[3-1][9];

이라는 것을 알 수 있습니다.

for 문을 사용해 바텀업 방식으로 각 오르막 수를 할당해 주면 답을 알 수 있습니다.

---

Description

• vector를 이용해 2중 배열을 동적할당하였습니다. (vector<vector<long long>>dp(N + 1, vector<long long>(10));)
• 마지막 N의 오르막 수의 개수라는 건 수의 길이가 N 일 때, 0으로 시작, 1로 시작, ... , 9로 시작의 모든 경우이므로 이를 결괏값에 더해주었습니다.
• MOD라는 상수를 만들어놓고 mod 연산을 진행했습니다.

---

#include <iostream>
#include <algorithm>
#include <vector>
#define MOD 10007
using namespace std;
int main(void) {
    int N;
    cin >> N;
    vector<vector<long long>>dp(N + 1, vector<long long>(10));
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= 9; j++) dp[i][j] = 0;
    }
    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 = j; k <= 9; 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;
    }
    cout << result << '\n';
    return 0;
}