[C/C++ 백준 11057번] 오르막 수 (Silver 1)

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

11057번: 오르막 수

길이 N과 시작수 i라 할때 만들수 있는 오르막 수를 dp[N][i]라 하자. i다음에 올수 있는 수는 i부터 9까지 가능하므로, 점화식은 for(int k=j; k<=9; k++){ dp[i][j] += dp[i-1][k]; } 이렇게 사용하면 된다. 정답은 N일때 dp[N][0] ~ dp[N][9]까지 모두 더해주면 된다.

---

#include <cstdio>
int main(void){
	int N, dp[1001][10]={{},{1,1,1,1,1,1,1,1,1,1},};
	int ans=0;
	scanf("%d",&N);
	for(int i=2; i<=N; i++){
		for(int j=0; j<=9; j++){
			for(int k=j; k<=9; k++){
				dp[i][j] += dp[i-1][k];
			}
			dp[i][j] = dp[i][j] % 10007;
		}
	}
	for(int q=0; q<=9; q++)	ans+=dp[N][q];
	printf("%d",ans%10007);
}

---