백준 1038 감소하는 수 (C++)

1038번: 감소하는 수

완전 탐색을 활용하여 문제를 풀었다. d[N]는 N번째 감소하는 수를 의미한다. 예를 들어 42?의 경우, 물음표에는 0과 1 즉 2개가 올 수 있다. 이를 통해 10으로 나눈 나머지만큼 감소하는 수가 있다는 것을 알 수 있다. 반복문을 통해 N번째 감소하는 수를 구하여 출력해주었다.

#include <iostream>

using namespace std;

int N;
long long d[1000001];

void solution() {
	if (N <= 10) {
		cout << N;
		return;
	}

	for (int i = 0; i < 10; i++) {
		d[i] = i;
	}

	int num = 10;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < d[i] % 10; j++) {
			d[num] = d[i] * 10 + j;
			num++;
		}
	}

	if (d[N] == 0) cout << -1;
	else cout << d[N];
}

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

	cin >> N;

	solution();
	
	return 0;
}