[백준 11057] 알고리즘 52일차 : 오르막 수

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

11057번: 오르막 수

 

동적계획법 C++

오르막수 구하기 문제

 

접근 방법

자리수 별로 오르막수를 저장하는 배열을 사용한다.

 

소스코드

#include <iostream>
using namespace std;

int main(){
    int n;
    cin >> n;
    int dp[1000][10]={0};
    for(int i = 0 ; i < 10 ; i++)
        dp[0][i] = 1;
    for(int i = 1 ; i < n ; i++){
        for(int j = 0 ; j < 10 ; j++){
            for(int k = j ; k < 10 ; k++){
                dp[i][j] = (dp[i][j]+dp[i-1][k]) % 10007;
            }
        }
    }
    
    int result = 0;
    for(int i = 0 ; i < 10 ; i++){
        result = (result+dp[n-1][i])%10007;
    }
    cout << result;
    return 0;
}