[solve.ac 골드5] 1038_감소하는 수

 

제한 사항

 

문제

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

입력

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

출력

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

 

---

나의 풀이

문제에서 0은 0번째, 1은 1번째 감소하는 수라고 했다. 즉, 한 자릿수는 모두 감소하는 수라고 할 수 있다.

2 자릿수 이상부터는 마지막 숫자보다 그 뒤에 붙는 숫자가 작아야 한다.

어떤 리스트에 감소하는 수를 저장한다고 하면 그 수 중 하나를 꺼낸 것이 만약 764라고 할 때 그 뒤에 붙일 수 있는 숫자는 3, 2, 1, 0으로 7643, 7642, 7641, 7640 이 감소하는 수로 리스트에 추가될 수 있다.

이렇게 만들 수 있는 감소하는 수는 최대 값이 정해져 있다. -> 9876543210 보다 큰 [감소하는 수]는 존재하지 않는다.

감소하는 수를 만드는 것은 다시 생각하면 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 의 숫자 중 n개를 중복 없이 뽑아서 감소하는 순으로 정렬하는 것이고, 중복 없이 숫자를 뽑는다면 감소하는 순으로 만들 수 있는 경우는 단 한 가지 이므로 n개를 중복 없이 뽑는 경우의 개수를 구하면 만들 수 있는 총 [감소하는 수]의 개수를 구할 수 있다.

 

감소하는 수의 개수

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 중 n개를 중복없이 뽑는 경우의 수를 구하는 것은 어렵지 않다.

각각의 숫자는 [뽑는다, 안 뽑는다] 두 상태 중 하나의 상태를 가지게 된다. 즉, 2가지 상태를 가질 수 있다.

숫자가 10개이므로 2^10을 하면 중복없이 뽑는 개수를 구할 수 있고, 그중 아무것도 뽑지 않는 한 가지 경우를 제외하면 감소하는 수의 개수는 2^10 - 1 이다.

nums = list(range(10)) # nums라는 리스트에 감소하는 수 저장 (한 자리 숫자로 초기화)
i = 1 # nums를 탐색하는 인덱스

while i < len(nums): # nums를 끝까지 탐색하기 위한 조건
    for n in range(nums[i]%10-1, -1, -1): # n은 nums의 i번째 숫자의 마지막 숫자보다 작은 수
        nums.append(nums[i]*10+n) # n을 nums의 i번째 숫자 뒤에 추가하여 nums에 추가
    i += 1 # 인덱스 증가

nums.sort() # nums 정렬

try:
    print(nums[int(input())]) # 입력 받은 수가 nums에 있는 수보다 작으면 출력
except:
    print(-1) # 그렇지 않다면 -1

 

 

채점 결과