[백준 1038] 감소하는 수 (Gold 5)

문제

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

접근

1. 숫자가 한 자리는 무조건 감소하는 수. 0부터 9까지 재귀함수를 먼저 돌려준다.
2. prev라는 재귀 이전의 숫자를 감소하는 수를 담은 리스트에 넣어준 다음 현재 숫자 보다 1이 작은 숫자들에 대해 재귀함수를 돌려준다.
3. 숫자가 0보다 작을 때 재귀를 멈춘다.
4. 리스트를 정렬하고 n을 인덱스로 값을 구한다. 단 n이 감소하는 수 리스트보다 크거나 같을 때는 -1을 반환한다.

Code

import sys

sys.setrecursionlimit(111111)

answer = 0
cnt = 0
arr = []
n = int(sys.stdin.readline())


def go(num, prev):
    if num < 0:
        return
    arr.append(int(prev))
    for i in range(num):
        go(num - i - 1, prev + str(num - i - 1))


for i in range(0, 10):
    go(i, str(i))

if len(arr) <= n:
    print(-1)
else:
    print(sorted(arr)[n])

여담

모처럼 쉬는 날이라 풀어봤는데 너무 오랜만에 풀어서 시간이 조금 걸렸다.재귀를 통한 완전탐색 문제들은 코딩테스트 2-3번 사이에 종종 나오므로 잘 숙지해 둘 것.