https://www.acmicpc.net/problem/1038
1038번: 감소하는 수
음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를
www.acmicpc.net
아 처음 시작을 잘못해서 조금 오래걸렸네요 2일 정도 ㅠㅠ 하아 문제 방향을 잘못 잡으면 이렇게 문제가 생기네요
키포인트는 9876543210이 감소하는 수의 제일 큰수이며 최대 1023회를 넘지 않습니다. 즉 백트레킹이 1023회를 넘지않는다. 그리고 조합이 0,1,2,3,4,5,6,7,8,9의 갯수로 조합을 통해서 숫자가 감소하는지 체크하면서 감소하면 백트래킹으로 넘겨줍니다. ㅠㅠ 어렵네요. 시작 방향을 잘못잡아서 문제가 되었네요 조합을 통하는게 아니라 숫자의 감소만 체크만해서 dfs로 넘기려고 했던게 문제였네요.
#include <iostream>
#include <vector>
#include <queue>
#include<string>
#include<algorithm>
#include<cmath>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;
struct Point {
int i, j;
int cnt = 0;
};
long long gcnt=-1;
//0,1,2,3,4,5,6,7,8,9
vector<int>stacks;
vector<bool>bvisitied;
vector<int>save;
long long n;
long long anw;
string maxstrt;
void backtracking(unsigned long long k, unsigned long long cnt) {
if (n >= 1023) {
maxstrt= "-1";
return ;
}
if (gcnt >= n) {
return ;
}
if (save.size()==k) {
gcnt++;
maxstrt = "";
for (int i = 0; i < save.size(); i++) {
maxstrt += (save[i] + '0');
}
return;
}
for(int i=0;i<10;i++)
{
if (bvisitied[i] == false) {
if (save.size() > 0) {
//검사
bool bCheck = false;
for (int j = 0; j < save.size(); j++) {
if ( save[j]< stacks[i]) {
bCheck = true;
break;
}
}
if (bCheck == true) {
continue;
}
}
bvisitied[i] = true;
save.push_back(stacks[i]);
backtracking(k,cnt+1);
save.pop_back();
bvisitied[i]=false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
if (n == 0) {
cout << 0;
return 0;
}
for (int i = 0; i <= 9; i++) {
stacks.push_back(i);
bvisitied.push_back(false);
}
for (int i = 1; i <= 10; i++)
{
backtracking(i, 0);
}
cout << maxstrt;
return 0;
}