백준 1174 줄어드는 수 Python

🐸 문제 정보

1174번: 줄어드는 수

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

60m+

 

📝 풀이

백트래킹을 오랜만에 풀어서 그런가 생각보다 어렵게 느껴지는 문제였다.

임시 배열을 두고, 가장 마지막 숫자와 비교하여 넣을 수 있는 수 들을 하나씩 채워나가면 풀 수 있었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
temps = []

def bt():
    if temps:
        res.append(int(''.join(map(str, temps))))
    for cur in range(10):
        if (not temps) or (cur < temps[-1]):
            temps.append(cur)
            bt()
            temps.pop()

try:
    res = []
    bt()
    print(sorted(res)[n - 1])
except:
    print(-1)