백준 - 2688번 : 줄어들지 않아 (C++)

풀이 방법 : DP

왼쪽 자릿수의 숫자가 오른쪽 자릿수보다 작거나 같은 숫자의 갯수를 구하는 문제다.
N이 1인 경우 0 ~ 9까지 10개다.

N이 2일때 가장 앞자리가 0인 경우 일의 자리가 0 ~ 9 까지인 경우가 가능하다.

가장 앞자리가 1인 경우 일의자리가 1~ 9까지 8개가 가능할 것이다.

계속 이런식으로 생각해보면
N자리 숫자의 가장 앞자리 숫자가 i인 경우의 줄어들지 않는 숫자의 갯수는
N-1자리 숫자의 가장 앞자리 숫자가 i ~ 9인 경우의 갯수의 합과 같을 것이다.
이대로 점화식을 세워서 해결해주면 된다.

#include <iostream>

using namespace std;

long long DP[65][10] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);
	
	for (int i = 0; i < 10; ++i)
	{
		DP[1][i] = 1;
	}

	for (int i = 2; i < 65; ++i)
	{
		for (int j = 0; j < 10; ++j)
		{
			for (int k = j; k < 10; ++k)
			{
				DP[i][j] += DP[i - 1][k];
			}
		}
	}

	int T;
	cin >> T;
	
	for (int i = 0; i < T; ++i)
	{
		int N;
		cin >> N;

		long long Answer = 0;
		for (int j = 0; j < 10; ++j)
		{
			Answer += DP[N][j];
		}

		cout << Answer << '\n';
	}
}