C++:: boj1174 < 줄어드는 수 >

잘 생각해보면 간단한 문제이다.

어렵게 생각해서 직접 수의 규칙성을 찾다가 시간을 꽤 버렸다. 나올수 있는 수의 개수가 그렇게 많지 않다는 점을 생각해보면 그냥 dfs를 해서 수를 만들어 줄 수 있다는 점을 알 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 줄어드는 수
vector<long long> answer;
int n;
void dfs(int last_num, long long res) {
	answer.push_back(res*10+last_num);
	for (int i=0; i<last_num; i++) {
		dfs(i, res*10+last_num);
	}
}

int main() {
	cin >> n;
	if (n > 1023) {// 만들 수 있는 수의 총 개수 1023 개
		cout << -1 << "\n";
		return 0;
	}
	for (int i=0; i<=9; i++) {
		dfs(i, 0);
	}
	sort(answer.begin(), answer.end());
	cout << answer[n-1] << "\n";
}