백준 1038

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

이 문제의 경우 문제 분류에 부르트 포스 라고 되어있지만 정확히는 dfs 백트래킹이라고 보는게 맞을거 같다 
처음에는 0 부터 9876543210 까지 수들을 검사해서 해당 수가 감소하는 수 인지를 검사하는 방법을 사용했지만 해당 방법은 시간초과를 유발했기에 dfs와 백트래킹을 사용하여 해당 문제를 풀었다

해당 이미지를 보자 우리가 백트래킹으로감소하는 수를 만들려고 할시 반복문의 범위를 단지 이전 자리의 숫자의 값까지만 증가시켜주면서 넣어주면 된다

#include <iostream>
using namespace std;
long  long arr[1000001];
long  long n;
long  long numCnt;
long  long idxOfNum = 10;
void makeDecreaseNum(long  long num , long  long numOfone , long  long cntOfNum) {
	if (cntOfNum==numCnt) {
		arr[idxOfNum] = num;
		idxOfNum++;
	}
	else {
		num = num * 10;
		for (long  long i = 0; i < numOfone; i++) {
			makeDecreaseNum(num + i, i, cntOfNum+1);
		
		}
	}

}
int main() {
	cin >> n;
	for (long  long i = 0; i < 1000001; i++) {
		arr[i] = -1;
	}
	for (long  long i = 0; i < 10; i++) {
		arr[i] = i;
	}
	for (long  long i = 2; i <= 11; i++) {
		numCnt = i;
		for (long  long j = 1; j <= 9; j++) {
			makeDecreaseNum(j, j, 1);
		}
	}
	cout << arr[n];
}