[C]백준 11057번 오르막 수

 

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

 

 

DP문제입니다.

 

N = 1 
1 1 1 1 1 1 1 1 1 1
N = 2 
10 9 8 7 6 5 4 3 2 1
N = 3
55 45 36 28 21 15 10 6 3 1
N = 4
220 165 120 84 56 35 20 10 4 1

 

제가 이해한 DP 규칙입니다.

 

소스

#include<stdio.h>
#pragma warning(disable:4996)
int main() {
int n;
scanf("%d", &n);
int dp[1001][10] = { 0, };
int sum = 0;
for (int i = 0; i < 10; i++) {
dp[1][i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 0; j < 10; j++) {
for (int k = 0; k <= j; k++) {
dp[i][j] = (dp[i][j] + dp[i - 1][k])%10007;
}
}
}
for (int i = 0; i < 10; i++) {
sum =(sum+dp[n][i])%10007;
}
printf("%d", sum);
}

 

배열을 0으로 초기화하지않으면 자꾸 값이 이상하게 나오더라구요

그래서 배열을 0으로 초기화했습니다.