[ C / C++ ] 백준 2688 줄어들지 않아

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

줄어들지 않는 4자리 수를 예를 들어 보면 0011, 1111, 1112, 1122, 2223이 있다. 줄어들지 않는 4자리수는 총 715개가 있다.

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

n이 주어졌을 때, 줄어들지 않는 n자리 수의 개수를 구하는 프로그램을 작성하시오.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define size 1000001

int t, n;
long long dp[65][10] = { 0 };

int main()
{
	for (int i = 0; i < 10; i++)
		dp[1][i] = 1;

	for (int i = 2; i <= 64; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			for (int k = j; k < 10; k++)
			{
				dp[i][j] += dp[i - 1][k];
			}
		}
	}
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d", &n);
		long long int s = 0;
		for (int i = 0; i < 10; i++)
			s += dp[n][i];
		
		printf("%lld\n", s);
	}
}