백준 1038 - 감소하는 수

https://www.acmicpc.net/problem/1038

처음에 DFS를 사용한 완전 탐색으로 구현했었다. 최종적으로 나올 수 있는 수 0~9876543210까지 전부 탐색해서 감소하는 N번째 수를 찾으면 탐색이 끝나도록 코딩하니 시간초과가 발생했다. 백트래킹을 사용해서 가지치기를 하려고하는데 조건이 바로 떠오르지 않아 시간을 많이 소비했다.. 질문 게시판에서 힌트를 얻었다. 조합을 사용해서 풀어보니 맞출수있었다.

우선 1(0~9)의 자리부터 시작해서 마지막으로 나올수 있는 수인 9876543210 10자리까지를 고를수 있다. 마지막 자릿수에 0~9가 올수있으며 다음에 오는 자릿수의 수가 이전에 선택한 자릿수의 값보다 작으면 감소하는 수가 아니므로 올 수 없도록 구현하여 감소하는 수들의 조합을 구하였다.아래는 해당 코드 부분이다.

for i in range(0, 9):
        if arr_num[-1]>i:
            arr_num.append(i)
            dfs(pick+1,N)
            arr_num.pop()

마지막 자릿수가 3으로 시작하는 감소하는 수의 조합이다.

3, 30, 31, 310, 32, 320, 321, 3210

마지막 자릿수가 0~9 인 값들을 통해 구한 감소하는 수의 조합을 숫자로 변경하여 배열에 저장하고 이를 정렬하여 N번째 감소하는 수를 찾을 수 있다.

N = int(input())
ret = []
arr_num = []

def convertArrToInt(arr):
    ret = ''
    for i in arr:
        ret += str(i)
    return int(ret)



# pick = 자리수
def dfs(pick, N):
    if pick == 10:
        ret.append(convertArrToInt(arr_num))
        return
    ret.append(convertArrToInt(arr_num))
    for i in range(0, 9):
        if arr_num[-1]>i:
            arr_num.append(i)
            dfs(pick+1,N)
            arr_num.pop()

if N >= 1023:
    print(-1)
else:
    for i in range(0,10):
        arr_num = [i]
        dfs(1,N)
    ret.sort()
    print(ret[N])