⭐ 감소하는 수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	22110	6712	5294	33.131%

문제

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 N번째 감소하는 수를 출력한다.

예제 입력 1

18

예제 출력 1

42

예제 입력 2

0

예제 출력 2

0

---

⭐ 풀이 과정

☑️ 감소하는 수

감소하는 수는,

[1, 2, 3, 4, 5, 6, 7, 8, 9, (한 자릿수일 때)
10, 20, 21, 30, 31, 32, 40, 41, 42, 43…. (두 자릿수일 때)
210, 310, 320, 321, 410… (세 자릿수일 때)
]

감소하는 수가 한 자리일 때를 먼저 구하고, 두 자리일 때를 구하고, 세 자리일 때를 구하는 방식으로 하면 된다.

➡️ depth = 1로 초기 설정하고, 구할 수 있는 수를 다 구한다. 이후에 depth를 +1 해주면서 구할 수 있는 수를 구하는 것을 반복한다.

☑️ N번째 감소하는 수가 없다면 -1을 출력한다.

감소하는 수 중에서 가장 큰 수는 9876543210이다. (열 자리 수가 최대라는 의미)

depth 를 증가시키는데 10보다 커진다면, 감소하는 수를 못찾았다는 의미이므로 -1 을 출력했다.

---

⭐ 코드

n = int(input())

decrease_num = [] # 감소하는 수가 들어갈 리스트

def dfs(depth, count):
    if count==depth:
        num = ""
        for i in result:
            num += str(i)
        decrease_num.append(int(num))
        return

    for i in range(0, 10):
        if len(result) > 0 : # 만약 i가 처음 들어가는 수가 아니면, 마지막 수를 살펴본다.
            if result[len(result)-1] > i: # i가 마지막 수보다 작은 경우만 넣는다. 
                result.append(i)
                dfs(depth, count+1)
                result.pop(-1)
        elif len(result) == 0: # 만약 i가 처음 들어가는 수라면 그냥 넣는다.
            result.append(i)
            dfs(depth, count+1)
            result.pop(-1)
            
depth = 1
while len(decrease_num) <= n:
    if depth > 10: # 감소하는 수 중에 가장 큰 수는 "9876543210"이므로 depth가 10보다 클 수 없다. 
        print(-1)
        exit()
    result = []
    dfs(depth, 0)
    depth += 1 

print(decrease_num[n])