문제에서 과연 몇번째 감소하는 수까지 존재하는 것일까? 잠깐 생각했을때는 감소하는 수는 무한히 존재할것 그렇지 않다. 결론적으로는 1023개, 1022번째 까지 가능하다.
{0,1,2,3,4,5,6,7,8,9}와 같은 집합이 있을때 이를 가지고 감소하는 수를 만들수 있는 경우는 몇가지 일까?
여기서 우리는 strictly decresing 한 경우만을 따지는 것이므로 위의 모든 부분집합은 감소하는 수를 오직 하나로 결정할수 있다. 단, 여기서 공집합은 제외를 하여야한다.
결과적으로 감소하는 수의 최대개수는 $2^{10}-1 = 1023$ 가 된다.
결과적으로 코드는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
static int count = -1;
static int target = 0;
public static long getNum(int len, int digit,long prevNum,int newNum){
if (digit == 0){
count++;
if (count == target){
return prevNum;
}
return -1;
}
for (int i=0;i<newNum;i++){
if (len > 1 && digit == len && i == 0){
continue;
}
long res = getNum(len,digit-1,prevNum*10+i,i);
if (res != -1){
return res;
}
}
return -1;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
target = Integer.parseInt(br.readLine());
if (target > 1022){
bw.write(-1+"\n");
bw.flush();
return;
}
int digit = 1;
long res = -1;
while (res == -1){
res = getNum(digit,digit,0,10);
digit+=1;
}
bw.write(res+"\n");
bw.flush();
}
}