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

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

 

문제

---

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

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

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

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

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

 

입력

---

첫째 줄에 테스트 케이스의 개수 T(1 <= T <= 1,000)이 주어진다. 각 테스트 케이스는 숫자 하나 n으로 이루어져 있다. (1 <= n <= 64)

 

출력

---

각 테스트 케이스에 대해 한 줄에 하나씩 줄어들지 않는 n자리 수의 개수를 출력한다.

 

문제 풀이

---

dp 문제.

2차원 배열 dp에 맨 마지막 숫자가 0부터 9까지인 i자리 수를 저장해두면 된다.

먼저 자리수가 1이라면 각 숫자가 1개씩 총 10개가 줄어들지 않는 수이다.

자리 수 2 중 끝자리가 0인 수는 자리수 1 중 끝자리가 0인수에 0을 붙이면 된다. 자리 수 2중 끝자리가 1인 수는 자리수 1 중 끝자리가 0인 수와 1인 수 각각에 1을 붙이면 된다. 자리 수 2중 끝자리가 2인 수는 자리수 1 중 끝자리가 0인 수와 1인 수, 2인 수 각각에 1을 붙이면 된다.

이를 일반화하면 자리수 i 중 끝자리가 j인 수는 자리수 i-1 중 끝자리가 0부터 j까지인 수 각각에 j를 붙이면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	long long** dp = new long long* [65];
	for (int i = 0; i < 65; i++)
	{
		dp[i] = new long long[10];
		for (int j = 0; j < 10; j++)
		{
			dp[i][j] = 0;
		}
	}
	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 = 0; k <= j; k++)
			{
				dp[i][j] += dp[i - 1][k];
			}
		}
	}
	for (int t = 0; t < T; t++)
	{
		int N;
		cin >> N;
		long long answer = 0;
		for (int i = 0; i < 10; i++)
		{
			answer += dp[N][i];
		}
		cout << answer << "\n";
	}

	return 0;
}