BOJ 11057번 오르막 수

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/11057/11057/%EC%86%8C%EC%8A%A4.cpp

 

오르막수는 작아지는 부분이 없는 수를 말한다.

ex) 0000, 0001, 3333, 9999

 

*길이가 1 일때는 기본적으로 0-9 으로 시작하는 모든 수는 1가지의 경우만 가지게 된다.

*시작하는수가 9인 경우 가능한 수는 9999... 밖에 없으므로 1가지의 경우만 가지게 된다.

 

초기화 후 손으로 직접 값을 그려보면

dp[시작하는 수][길이] = dp[시작하는수][길이-1] + dp[시작하는수-1][길이] 라는 점화식을 유추해낼 수 있다.

 

#include <iostream>
using namespace std;
 
int dp[10][1001];
int N;
 
int main() {
    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++) dp[0][i] = 1;
     
    for (int k = 2; k <= N; k++)
        for (int i = 1; i < 10; i++)
            dp[i][k] = (dp[i-1][k]+dp[i][k-1])%10007;
 
    int total = 0;
    for (int i = 0; i < 10; i++) total += (dp[i][N])%10007;
    cout << total%10007;
    return 0;
}