문제 풀이

백트래킹 형식으로 푼 문제, 맨 앞쪽 자리수부터 채워나가면서 진행해준다.
크게 최대 자리수가 한 자리 수이고 맨 앞자리 수를 채워야할 때, 최대 자리수가 한 자리 수가 아니고 맨 앞자리 수 를 채워야할 때, 그 외 맨 앞자리 수를 채울 때가 아닐 때로 나누어,
최대 자리수가 한 자리 수이고 맨 앞자리 수를 채우고 있다면 0부터 9를 채우면 되고,
최대 자리수가 한 자리 수가 아니고 맨 앞자리 수를 채우고 있다면 1부터 9까지 채우면된다.
그 외 맨 앞자리 수를 채우고 있지 않는다면 현재 자리 수의 이전 자리 수보다 작은 숫자들을 차례대로 채워 나간다. 9876543210이 존재하는 수 중에 가장 큰 감소하는 숫자이고 n은 1022이다
그러므로 1023이상의 입력에는 -1을 출력하면된다.

문제 링크

boj/1038

소스코드

PS/1038.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<math.h>
using namespace std;

vector<int> v;
int n, cnt;
int dfs(int idx, int max);
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> n;
	if (n >= 1023)
		cout << -1;
	else
	dfs(0, 1);
}
int dfs(int idx, int max)
{
	if (idx == max)
	{
			if (cnt == n) {
			for (int i = 0; i < v.size(); i++)
			{
				cout << v[i];
			}
			return (0);
		}
		cnt++;
		return 1;
	}
	if (max != 1 && idx == 0)
	{
		for (int i = 1; i <= 9; i++)
		{
			v.push_back(i);
			int ret = dfs(idx + 1, max);
			v.pop_back();
			if (ret == 0)
				return (0);
		}
		dfs(0, max + 1);
	}
	else if (max == 1 && idx == 0)
	{
		for (int i = 0; i <= 9; i++)
		{
			v.push_back(i);
			int ret = dfs(idx + 1, max);
			v.pop_back();
			if (ret == 0)
				return (0);
		}
		dfs(0, max + 1);
	}
	else if (idx != 0)
	{
		for (int i = 0; i <= 9; i++)
		{
			if (v.back() <= i)
				continue;
			v.push_back(i);
			int ret = dfs(idx + 1, max);
			v.pop_back();
			if (ret == 0)
				return (0);
		}
	}

	return (1);

}