풀이
점화식을 세우자!
dp[수열의 자릿수 i][i번째 자릿수의 숫자 j] 일 때의 경우의 수
dp[i][j] = dp[i-1][j] + dp[i][j-1]
코드
#include <stdio.h>
const int mod = 10007;
int n, i, j, ans, dp[10001][10];
int main() {
scanf("%d", &n);
for (i = 0; i <= 9; i++) dp[1][i] = 1;
for (i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][0];
for (j = 1; j <= 9; j++) {
dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
}
}
for (i = 0; i <= 9; i++) {
ans = (ans + dp[n][i]) % mod;
}
printf("%d", ans);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge