티스토리 뷰

728x90

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

 

11057번: 오르막 수

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수�

www.acmicpc.net

 

동적계획법 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;
}
728x90
250x250
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/02   »
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29
글 보관함