BOJ - 1038번 감소하는 수(C++)

문제 출처: https://www.acmicpc.net/problem/1038

문제 난이도

Gold 5

문제 접근법

점점 감소하는 수니깐, 제일 큰수부터 작은 수로 깊이 들어가는 탐색법을 사용했다.
9876543210까지 들어가니깐 int형으로는 틀렸습니다가 뜨니깐 long long 형으로 썼다.

통과 코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>


using namespace std;

vector<long long> lessNum;

void dfs(long long num, int cnt) {
	if (cnt == 10) return;
	lessNum.push_back(num);
	for (int i = 0; i < 10; i++) {
		if (num % 10 > i) dfs(num * 10 + i, cnt + 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N;
	cin >> N;
	for (int i = 0; i < 10; i++) {
		dfs(i, 0);
	}
	sort(lessNum.begin(), lessNum.end());

	long long ans = lessNum.size() > N ? lessNum[N] : -1;

	cout << ans << "\n";
	
	return 0;
}

피드백

처음엔 브루트포스 혹은 DP라고 생각하다 점화식을 세우기 어려워서 브루트포스로 9876543까지 돌렸다. 그 이상으로 돌리니깐 시간초과가 나고 답이 안나와 틀렸습니다가 뜨기도 했다. 조금 더 고차원적으로 생각할 필요가 있다!