[BOJ/11057] 오르막 수

(공감과 댓글 하나는 글쓴이에게 큰 힘이 됩니다.)

 

문제 링크

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

 

사용 알고리즘

- DP

 

풀이

- d[i][j] = i자리 오르막 수의 개수, i번째 자리의 수는 j

- d[1][i] = 1

- d[i][j] += d[i - 1][k] (0 <= k <= j)

 

소스 코드

- https://github.com/moomini/algorithm/blob/master/boj/11057.cpp

#include <cstdio>   int d[1003][10];   int main(void) {     int n; scanf("%d", &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] %= 10007;             }         }     }     int ans = 0;     for (int i = 0; i <= 9; ++i) {         ans += d[n][i];         ans %= 10007;     }     printf("%d\n", ans);     return 0; } Colored by Color Scripter

cs