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

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

2688번: 줄어들지 않아

문제

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

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

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

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

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

 

 

전형적인 재귀함수로 완전탐색하는 문제처럼 보인다.

하지만 여기에 메모이제이션만 적용시켜주면 복잡도 면에서 개선이 되기에 동적계획법으로 해결하였다.

 

특정한 자리(인덱스)에서의 특정한 수(0~9)가 가질 수 있는 모든 경우의 수를 메모이제이션 적용시켜주면 중복되는 탐색을 방지할 수 있다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 100000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
ll cache[66][10];

ll solution(int cur, int index) {
	if (index == N) return 1;
	ll& ret = cache[index][cur];
	if (ret != -1) return ret;
	ret = 0;
	ret += solution(cur, index + 1);
	for (int next = cur + 1; next < 10; next++) {
		ret += solution(next, index + 1);
	}
	return ret;
}

void input() {
	int testCase;
	cin >> testCase;
	while (testCase--) {
		cin >> N;
		memset(cache, -1, sizeof(cache));
		cout << solution(0, 0) << endl;
	}
}

int main() {
	fastio;
	input();

	return 0;
}