반응형
알고리즘 분류 : 다이나믹 프로그래밍
오르막 수를 DP로 구현하는 문제다. 오르막 수란 각 자리의 수가 오름차순을 이루는 숫자를 말한다. 0으로 시작할 수 있으며, 인접한 자리의 숫자가 같아도 오르막 수이다.
- D[N][M] : M으로 끝나는 N자리 오르막 수
- D[1][0] = 1, D[1][1] = 1, ‥‥ , D[1][9] = 1
- D[N][0] = D[N-1][0] : 0으로 끝나는 N자리 오르막 수
- D[N][1] = D[N-1][0] + D[N-1][1]
- D[N][2] = D[N-1][0] + D[N-1][1] + D[N-1][2]
- ‥‥
- D[N][9] = D[N-1][0] + D[N-1][1] + ‥‥ + D[N-1][9]
C++ 소스코드
#include <cstdio> int n, ans; int d[1001][10]; const int mod = 10007; void solve() { 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; } } for (int i=0; i<=9; i++) ans += d[n][i]; printf("%d\n", ans%mod); } int main() { scanf("%d", &n); solve(); return 0; }
Python 3 소스코드
n = int(input()) d = [[0]*10 for _ in range(n+1)] mod = 10007 def solve(): for i in range(10): d[1][i] = 1 for i in range(2, n+1): for j in range(10): for k in range(j+1): d[i][j] += d[i-1][k] d[i][j] %= mod solve() print(sum(d[n])%mod)
참고
- 백준 온라인 저지 : BOJ 11057
반응형