[Python] BOJ / 1038번 / 감소하는 수

1038번: 감소하는 수

---

📝 풀이

• 백트리킹 알고리즘 사용
  • 재귀로 구현할 경우 메모리 초과가 발생하므로 while문을 통해 구현
• 알고리즘
  • 현재 값이 감소하는 수라면 현재 값에 +1을 수행
  • 현재 값이 감소하는 수가 아니라면 현재 값과 가장 가까운 감소하는 수가 되도록 수정
  • 위 과정을 반복하며 N번째 감소하는 수가 되었을 때의 값을 출력
  • N번째 감소하는 수가 없는 경우에는 -1을 출력해야하며 ,이는 최대 감소하는 수인 '9876543210'보다 현재 값이 클 경우임

---

💻 소스코드

import sys

input = sys.stdin.readline
MAX = 9876543210

def solve():
    cnt = num = 0
    while True:
        if num > MAX:
            return -1

        flag = True
        str_num = str(num)

        for i in range(1, len(str_num)):
            if int(str_num[i - 1]) <= int(str_num[i]):
                left = str_num[:i - 1]
                mid = str(int(str_num[i - 1]) + 1)
                right = '0' + str_num[i + 1:]
                num = int(left + mid + right)
                flag = False
                break
        
        if flag:
            if cnt == n:
                return num
            cnt += 1
            num += 1

n = int(input())

print(solve())