자리수에 따라 숫자가 감수하는 수 중 n번째 수를 구하라 (ex. 321, 5210...)
- 자리수를 key값으로 가지는 딕셔너리를 만들고 해당 자리수의 줄어드는 값을 넣는다.
- dfs를 통해서, 현재 자리수 줄어드는 값을 탐색하고, 현재 자리수 0번 인덱스 숫자보다 큰 숫자를 앞에 더한다.(이 때, 문자열로 형변환하여 더한다.)
- 9876543210보다 큰 줄어드는 수는 없기 때문에 10번째 자리수까지만 구한다.
n = int(input())
my_dict = {}
# 딕셔너리에 자리수 별 줄어드는 수를 넣을 set을 넣는다.
for i in range(1,11) :
my_dict[i] = set()
# 1번째 자리수 초기값만 add해준다.
for i in range(10) :
my_dict[1].add(i)
# 재귀로 10번째 idx까지 찾을 예정
def solve(idx) :
if idx == 10 :
return
# 현재 idx의 값에서 다음 자리수 줄어드는 수를 구해 넣어준다.
for i in my_dict[idx] :
i = str(i)
for j in range(int(i[0])+1,10) :
num = str(j)+i
my_dict[idx+1].add(num)
solve(idx+1)
solve(1)
answer = list()
# answer 배열에 구해준 줄어드는 수를 넣어주고
for i in range(1,11) :
for j in my_dict[i] :
answer.append(int(j))
# 만약 answer보다 n이 크다면 -1을
if len(answer) < n :
print(-1)
else :
# 아니라면 answer[n-1]을 print한다.
answer.sort()
print(answer[n-1])