오르막 수 C++ - 백준 11057

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

이 문제의 dp 테이블은 백준 쉬운 계단 수와 그냥 동일하다.

같은 방식으로 0~9의 개수를 탐색하고 dp 테이블에 저장한다.

사실 조합으로도 풀 수 있고, 다른 점화식으로도 풀 수 있었다.

조합

9+nCn

dp[n]=dp[n-1]*(n+9)/n

코드는 다음과 같다.

#include <iostream>
#define MOD 10007
typedef long long ll;
using namespace std;

ll dp[1000][10];
int n;

int main(){
	cin >> n;
	for(int i=0;i<10;i++){
		dp[0][i]++;
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<10;j++){
			for(int k=0;k<=j;k++){
				dp[i][j]+=dp[i-1][k]%MOD;
			}
		}
	}
	ll ans=0;
	for(int i=0;i<10;i++){
		ans+=dp[n-1][i]%MOD;
	}
	cout << ans%MOD;
}