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

백준

---

🤔문제 이해

0이 맨 앞에 올 수 있으므로 1~N자리의 숫자 중 i번째 숫자가 i+1번째 숫자보다 작거나 같은 수의 개수를 구하는 문제이다. 

---

💡첫번째 아이디어

일단 맨 처음에 0이 오고 그 다음에 올 수 있는 숫자들을 나열해 봤다. 

N이 커질수록 중복되는 값들이 보였고 DP 문제임을 확신했다!

 

🔥풀이🔥

dp[i][j]에서 i는 맨 처음에 올 수 있는 수로 0~9까지를 나타내고, j는 자릿수를 의미한다.

자릿수가 j일 때 dp[0][j]는 dp[0][j-1] ~ dp[9][j-1]까지의 값을 다 더한 값이다.

구하고자 하는 자릿수까지 dp를 채웠으면 마지막으로 그 자릿수로 만들어지는 처음 숫자가 0~9까지인 숫자들의 개수를 다 더한다.

모든 dp연산과 마지막 총합, 출력까지 %10007 연산을 해주어 계산 결과가 int 범위를 벗어나지 않게 해준다.

 

❌트러블 슈팅

일단 dp[0][1] ~ dp[9][1]까지 1로 초기화해주었기 때문에 3중 for문에서는 자릿수 2부터 시작해줘야 했다. 어차피 dp[][0]값은 0이므로 상관없긴 했지만..그리고 가장 큰 실수로는 마지막으로 결과 값을 출력할 때 %10007 연산을 해주지 않았다. 

---

#include <iostream>

using namespace std;

int dp[11][1001];
int n;

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> n;

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

    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            for (int k = j; k < 10; k++) {
                dp[j][i] += dp[k][i - 1] % 10007;
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 10; i++) {
        ans += dp[i][n] % 10007;
    }
    cout << ans % 10007;
}