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

문제

오르막 수

코드

#include <iostream>

using namespace std;

int N;
int dp[1001][10];

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

    cin >> N;

    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++){
            for (int k = j; k < 10; k++){
                dp[i][k] += dp[i-1][j];
                dp[i][k] %= 10007;
            }
        }
    }

    int sum = 0;
    for (int i = 0; i < 10; i++) sum += dp[N][i];

    cout << sum % 10007;

    return 0;
}

접근

이 문제를 보고 나름 자연스럽게 dp로 풀어야겠다고 생각이 들었다. 이전 단계에서 오르막의 규칙이 지켜진다면 앞으로도 지켜질 것이기 때문에 이전 값을 이용할 수 있기 때문이다. 그래서 dp 배열을 사용하였다.

dp[i][10] : i 자리의 숫자 중 0~9로 끝날 수 있는 수의 개수

만약 마지막 자리가 0이라면 이때 고려해야 하는 값들은 dp[i-1][0~9]이고, 마지막 자리가 8이라면 고려해야 하는 값들은 dp[i-1][8~9]이다. 따라서 이를 위해서 3중 for문을 사용하였다. 또한 1자리 숫자들의 경우도 만족할 수 있게 먼저 값을 1로 처리해주었다.