1038

날짜 : 2023. 04. 26

사용 언어 : python

 

문제

 

 

코드

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline())
if n == 0:
    print(0)
    exit()
a = list()


def dfs(num):
    #print(num)
    a.append(int(num))
    for i in range(int(num[-1])-1, -1, -1):
        t = int(num + str(i))
        dfs(str(t))  # 내림수 생성
    return

for i in range(9, 0, -1):
    dfs(str(i))

if len(a) < n:
    print(-1)
else:
    a.sort()
    #print(a)
    print(a[n-1])

 

 

풀이

- 재귀함수를 사용해 숫자의 가장 끝자리수보다 작은 수를 생성하는 방식으로 생성한다.

ex) 9 -> 8

         -> 7

         -> 6

         -> 5

         -> 4

         -> 3

         -> 2

         -> 1

         -> 0

- 그 후 내림수를 미리 만든 리스트에 전부 포함시키고, 정렬 후 값을 출력한다.

 

 

알게된 점

- DFS를 활용해 풀이했지만 계속 뭔가 틀렸다.

- 메모리초과도 뜨고, 정답도 틀리게 나와서 뭘까 고민했는데 처음에는 True, False를 활용해 모든 수에 대한 내림수 여부를 조사한 것이 원인이었다.

- 그래서 내림수만 체크하기 위해 리스트(a)를 만들었고, 인덱스 단위로 비교하는 방식으로 풀이했더니 바로 정답을 받았다.

- DFS를 활용했기 때문에  TLE 측면에서는 크게 문제되지는 않았다.

 

 

참고 사이트

-