백준 2688 줄어들지 않아

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

백준 2688 줄어들지 않아 

이 문제는 뒤로 갈 수록 숫자가 줄어들면 안되는 숫자의 개수를 구하는 것이 문제이다. 

 

숫자가 한자리 수일 때 

 

0 1 2 3 4 5 6 7 8 9

1  1 1  1  1 1  1  1  1  1

 

한자리 수 일때는 모두 1개만을 갖고 있다. 두자리 수가 될 때는 두번째 값 전 첫번째 값은 두번째 값 보다 같거나 작아야한다. 따라서 아래와 같은 점화식이 나오게 된다.

 

dp[i][5] = dp[i-1][5] + dp[i-1][4] + dp[i-1][3] + dp[i-1][2] + dp[i-1][1] + dp[i-1][0];

dp[i][1] = dp[i-1][1] + dp[i-1][0];

 

그러니 즉 두번째 값 보다 작거나 같은 값들을 더해주면 된다. 

#include <cstdio>
#define ll long long
ll dp[67][10];

void solve();
void init();

int main(){
	int T, N;
	ll result = 0;
	scanf("%d", &T);
	init();
	solve();
	for(int i = 0; i < T; i++){
		result = 0;
		scanf("%d", &N);
		for(int j = 0; j <= 9; j++)
			result += dp[N][j];
		printf("%lld\n", result);
	}
}

void init(){
	for(int i = 0; i <= 9; i++)
		dp[1][i] = 1;
}	

void solve(){
	for(int i = 2; i <= 64; i++){
		for(int j = 0; j <= 9; j++){
			for(int k = 0; k <= j; k++)
				dp[i][j] += dp[i-1][k];
		}
	}
}