BOJ 11057 - 오르막수

pa324·2019년 11월 7일
0

문제

풀이

  • 오르막 수는, 수의 자리가 오름차순을 이루는 수를 의미한다.
  • 앞자리와 같은 수도 오름차순으로 생각한다.
  1. n = 1
1,2,3,4,5,6,7,8,9

dp[1][1] = 1
dp[1][2] = 1
dp[1][3] = 1
dp[1][4] = 1
dp[1][5] = 1
dp[1][6] = 1
dp[1][7] = 1
dp[1][8] = 1
dp[1][9] = 1

  1. n = 2
11,12,13,14,15,16,17,18,19
22,23,24,25,26,27,28,29
33,34,35,36,37,38,39
44,45,46,47,48,49
66,56,57,58,59
66,67,68,69
77,78,79
88,89
99

dp[2][1] = 9
dp[2][2] = 1
dp[2][3] = 1
dp[2][4] = 1
dp[2][5] = 1
dp[2][6] = 1
dp[2][7] = 1
dp[2][8] = 1
dp[2][9] = 1

dp[1] = 9
dp[2] = 55

코드

#include <iostream>
using namespace std;
long long d[1001][10];
long long mod = 10007;
int main() {
    int n;
    cin >> n;
    for (int i=0; i<=9; i++) {
        d[1][i] = 1;
    }
    for (int i=2; i<=n; i++) {
        for (int j=0; j<=9; j++) {
            for (int k=0; k<=j; k++) {
                d[i][j] += d[i-1][k];
                d[i][j] %= mod;
            }
        }
    }
    long long ans = 0;
    for (int i=0; i<10; i++) {
        ans  += d[n][i];
    }
    ans %= mod;
    cout << ans << '\n';
    return 0;
}
profile
안녕하세요

0개의 댓글