백준 1174 - 줄어드는 수

문제요약

자리수에 따라 숫자가 감수하는 수 중 n번째 수를 구하라 (ex. 321, 5210...)

풀이요약

1. 자리수를 key값으로 가지는 딕셔너리를 만들고 해당 자리수의 줄어드는 값을 넣는다.
2. dfs를 통해서, 현재 자리수 줄어드는 값을 탐색하고, 현재 자리수 0번 인덱스 숫자보다 큰 숫자를 앞에 더한다.(이 때, 문자열로 형변환하여 더한다.)
3. 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])