백준 BOJ 11057 - 오르막 수

www.acmicpc.net/problem/11057

11057번: 오르막 수

이 역시 2차원 디피문제이다.

무난하게 풀었다.

 

dp[i][j]는 길이가 i인 숫자의 마지막이 j일때 만들어지는 오르막 수의 개수이다.

즉 수의 길이가 N인 오르막 수의 개수를 구하려면 dp[n][0]부터 dp[n][9]까지 더해주고

10007로 나눈 나머지를 출력해주면 깔끔하게 AC가 나오게 된다

주의할만한점으로는

계산도중에 int범위를 넘어갈거같지는 않아도

습관들이는 느낌으로다가 항상 dp문에도 mod연산을 해주는것이 중요하다.

 

#include <stdio.h>

int dp[1234][11] = {0};

int main(){
	int n;
	scanf("%d", &n);
	
	for(int i=0; i<10; i++) dp[1][i] = 1;
	for(int i=2; i<=n; i++){
		for(int j=0; j<=9; j++){
			for(int k=j; k<=9; k++){
				dp[i][k] =(dp[i][k] + dp[i-1][j]) % 10007;
			}
		}
	}
	int ans = 0;
	for(int i=0; i<10; i++) ans += dp[n][i];
	printf("%d", ans%10007);
	return 0;
}