BOJ 11057 - 오르막 수

문제

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

수의 길이 N이 주어졌을때 0부터 N사이에서 첫번째 자리부터 마지막 자리까지 내림차순으로 진행되지 않는 수를 찾는것이다.

예를들어 2234, 2999는 오름차순으로 진행되는 수지만 2167은 중간 1이 왼쪽의 1보다 작으므로 해당되지 않는다.

규칙

$ dp[1][0]=dp[1][1]=...=dp[1][9]=1 $ 이고 $ 2 ≤ N $ 일때

dp[N] = $ \sum\limits_{i=0}^9 dp[N-1][i] + \sum\limits_{i=1}^9 dp[N-1][i] + ... + dp[N-1][9] $ 

단 문제에서 출력을 10007로 나눈 나머지를 출력하라 하였으니 매번 계산할때마다 10007로 나누어주어야 한다.

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