난이도

Gold 5

인증

문제

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

입력

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

출력

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

예제 입력

예제 출력

해설 및 후기

나올 만한 숫자가 상당히 적어서 이렇게 풀어도 되나? 싶을 정도로 작성해봤는데 빠르게 풀렸다. 의도한 문제 풀이는 이러한 방식이 아닐 것 같지만, 어쨋든 최대 10자리의 수만 만들 수 있으므로, 모든 경우의 수를 구해 정렬해서 답을 구한다.

제출 코드

n = int(input())
cnt = 0
l = []
def cng(ls):
    i = 0
    rev = []
    ans = 0
    while(i < 10):
        if(ls[i] == -1):
            i+=1
            continue
        rev.append(ls[i])
        i += 1
    for j in range(len(rev)):
        ans += rev[j]*10**(j)
    return ans

for i1 in range(-1, 10):
    for i2 in range(-1 if i1 == -1 else i1+1,10):
        for i3 in range(-1 if i2 == -1 else i2+1,10):
            for i4 in range(-1 if i3 == -1 else i3+1,10):
                for i5 in range(-1 if i4 == -1 else i4+1,10):
                    for i6 in range(-1 if i5 == -1 else i5+1,10):
                        for i7 in range(-1 if i6 == -1 else i6+1,10):
                            for i8 in range(-1 if i7 == -1 else i7+1,10):
                                for i9 in range(-1 if i8 == -1 else i8+1,10):
                                    for i10 in range(-1 if i9 == -1 else i9+1,10):
                                        l.append(cng([i1,i2,i3,i4,i5,i6,i7,i8,i9,i10]))

l.sort()
try:
    print(l[n+1])
except:
    print(-1)