PS/문제풀이

백준 1174 줄어드는 수 Python

중규리 2024. 1. 8. 15:40

🐸 문제 정보

 

1174번: 줄어드는 수

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는

www.acmicpc.net

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

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)