[백준] 11057번 : 오르막 수

 

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

11057번: 오르막 수

---

 

DP 문제!!

 

조건에 따라 오르막 숫자의 개수를 아래와 같이 계산해보면,

	0으로끝남	1로끝남	2로끝남	3으로끝남	4로끝남	5로끝남	6으로끝남	7로끝남	8로끝남	9로끝남
0	-	-	-	-	-	-	-	-	-	-
1자리숫자	1	1	1	1	1	1	1	1	1	1
2자리숫자	1	2	3	4	5	6	7	8	9	10
3자리숫자	1	3	6	10	15	21	28	36	45	55

 

규칙이 보인다!!

편의상 0행은 비워두고 1행부터 채웠다.

 

i=1일 때, 오르막수는 전부 1이다.

 

i>=2일 때, 0으로 끝나는 수는 00, 000, 0000 ... 이므로, 무조건 1이다.

나머지의 경우, dp[i][j] = dp[i][j-1] + dp[i-1][j]임을 어렵지 않게 알 수 있다.

 

 

#include <iostream>

using namespace std;

int main(){
	int c = 10007;
	
	int n; cin>>n;
	int dp[n+1][10];	//행:1~10, 열:0~9 
	
	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++){
			if(j==0) dp[i][j]=1;
			else {
				dp[i][j]=dp[i][j-1]+dp[i-1][j];
				dp[i][j] %= c;
			}
		}
	}
	
	int sum=0;
	for(int i=0;i<10;i++){
		sum += dp[n][i];
	}
	
	cout<< sum % c;
	
	return 0;
}