[백준/파이썬] 1038번 감소하는 수

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

1038번: 감소하는 수

 

문제 해석

 

감소하는 수가 되는 n번째 수를 구하는 문제이다.

---

코드

 

# from collections import deque
input = __import__('sys').stdin.readline

# input
n = int(input())


# 해당 배열이 감소하는 수 인지 확인
def check(i):
	global num
	if len(num) == 1: return 1
	if num[-2] > i: return 1
	else: return 0

num = []
ans = []
def dfs(depth):
	global num
	for i in range(10):
		num.append(i)
		if check(i):
			dfs(depth + 1)
			ans.append(int(''.join(str(x) for x in num)))
		num.pop()
	
dfs(0)
ans.sort()

# 감소하는 수는 1022개 존재 그외는 -1 출력
if n >= len(ans): print(-1)
else: print(ans[n])

---

문제 풀이

 

먼저 감소하는 수는 0부터 시작한다.

0, 1, 2, 3, 4 ,5 ~ 10, 20, 21 순으로 나열되며 마지막 감소하는 수는 9876543210이 된다.

수가 많지 않아 모든 수를 구해 배열에 넣은 뒤 정렬하는 방법을 사용했다.

 

감소하는 수는 추가된 수가 추가된 수의 앞의 수 즉 기존의 num[-2] 보다 작으면 ans 배열에 추가해주었다.

 

9876543210은 1022번째 감소하는 수이며 0을 포함해 1023개 존재하게 된다. 따라서 1023 이상의 값이 입력되면 -1을 출력하도록 풀어주었다.