접근방법

우선, 이 문제에서 감소하는 수의 최대값은 9876543210 이다.
최대값은 90억이 넘어가므로, 모든 경우를 다 탐색하기에는 무리이다.
백트래킹을 활용하여 더이상 탐색할 필요가없는 부분은 제외시켜야 한다.

Solution

나는 백트래킹을 활용해서 문제를 풀었지만, 풀이방법은 다양하다.

1. combinations 라이브러리를 사용하는 풀이.

감소하는 수 이므로, 모든 조합을 구한 후에 , 각 조합의 내림차순 결과를 집합에 넣어준다.

from itertools import combinations
N = int(input())

nums = set()
for i in range(1, 11):
    for comb in combinations(range(0,10),i):
        comb = list(comb)
        comb.sort(reverse = True)
        nums.add(int(''.join(map(str,comb))))

sor_nums = sorted(nums)
try:
    print(sor_nums[N])
except:
    print(-1)

2. 백트래킹 풀이.

백트래킹이란 한정 조건을 가진 문제를 푸는 전략이다. 모든 경우의 수에서 한정 조건에서의 모든 경우의 수를 시도하는 것이다.
백트래킹을 활용하여, 1자릿수, 2자릿수, 3자릿수….10자릿수 까지 모두 ans배열에 넣어서 ans배열을 sort시킨후 정답을 출력한다. 즉, 여기서의 한정조건은 자릿수 이다.

N = int(input())
result = []
ans = []
def BackTrack(x,M):
    if len(result) ==M:
        ans.append(int(''.join(map(str,result))))
        return

    for i in range(x,-1,-1):
        result.append(i)
        BackTrack(i-1,M)
        result.pop()

for i in range(1,11):
    BackTrack(9,i)
ans.sort()

if N >= len(ans):
    print(-1)
    exit()
else:
    print(ans[N])

하지만 한정 조건을 자릿수로 설정하기에는,처음부터 아이디어가 잘 떠오르지 않을거 같다고 생각했다. 다음은 한정 조건을 감소하는 수 로 설정했을때의 코드이다.

N = int(input())
result = []
ans = []

def check(result):
    if len(result) == 1:
        return 1
    elif len(result) == 0:
        return 1
    elif result[-2] <= result[-1]: 
        return 0
    return 1

def BackTrack():
    if not check(result) or len(result) > 10: # 감소하는 수가 아니거나, 자릿수가10을 넘어가면 종료
        return
    else:
        if len(result) != 0:
            ans.append(int(''.join(map(str,result))))

    for i in range(10):
        result.append(i)
        BackTrack()
        result.pop()

BackTrack()
ans.sort()
print(ans[N])

3. DFS 풀이

다른사람이 DFS를 활용하여 푼 코드이다.

# input
n = int(input())

# 해당 배열이 감소하는 수 인지 확인
def check(i):
	global num
	if len(num) == 1: return 1
	if num[-2] > i: return 1
	else: return 0

num = []
ans = []
def dfs(depth):
	global num
	for i in range(10):
		num.append(i)
		if check(i):
			dfs(depth + 1)
			ans.append(int(''.join(str(x) for x in num)))
		num.pop()
	
dfs(0)
ans.sort()

# 감소하는 수는 1022개 존재 그외는 -1 출력
if n >= len(ans): print(-1)
else: print(ans[n])

Reference:

https://ddingmin00.tistory.com/entry/백준파이썬-1038번-감소하는-수

https://ryu-e.tistory.com/59