백준 2688번 줄어들지 않아 C++

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

 

다이나믹 프로그래밍으로 문제를 해결하였다.

dp[i][j] 의 2차원 dp배열을 만들고 이 배열의 의미는 i자리 수의 마지막 숫자가 j일 때 줄어들지 않는 수의 개수이다.

i자리 수의 마지막 숫자가 j일 때 줄어들지 않는 수의 개수는 i-1자리 수의 마지막 숫자가 0~j일 때 줄어들지 않는 수들의 합이다. 즉, dp[i][j] = dp[i-1][0] + .... + dp[i-1][j] 이다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;
using ull = unsigned long long;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<vector<ull>> dp(65, vector<ull>(10));
	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++) {
			ull sum = 0;
			for (int k = 0; k <= j; k++) {
				sum += dp[i - 1][k];
			}
			dp[i][j] = sum;
		}
	}

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		ull ans = 0;
		for (int i = 0; i < 10; i++) {
			ans += dp[n][i];
		}
		cout << ans << "\n";
	}
};