백준 1038 감소하는 수

문제 링크

문제 해결

N번째 감소하는 수가 몇인지 출력하는 문제, N은 최대 100만까지 입력된다.
간단하게 0부터 987654321까지 감소하는 수인지 판별하는것은 시간초과가 나오므로, 감소하는 수의 특성을 이용하여 풀어야한다.
감소하는 수는 955같이 중복이 나오면 안되고 맨 앞자리의 수에 의해 나머지가 결정된다. 예를들어 특정 감소하는 수가 5로 시작된다면 나머지는 반드시 {1,2,3,4}의 조합으로 이루어져야 한다. 이런 성질을 이용해서 1부터 10까지 대표 앞자리를 설정한 후 각 앞자리마다 파생되는 나머지 숫자들을 조합하면 된다.

1
10
21 -> 210 -> 
20 -> 20
32 -> 321 -> 3210
   -> 320
31 -> 310
30
43 -> 432 -> 4321 -> 43210
   -> 431
   -> 430
   ...

위 처럼 숫자가 올라갈수록 파생되는 수가 많아진다.

이를 구현하기 위해 각 숫자를 ‘1’, ‘0’과 같이 문자 리스트로 변환 후 마지막 자리의 수에서 계속 파생되도록 재귀 호출 방식을 사용하였다.

모든 감소하는 수를 구한 후, 오름차순 정렬 후 N번째 감소하는 수를 구하면 된다.

또한, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }에서 공집합을 제외한 모든 부분집합의 갯수는 $$ 2^{10} - 1 = 1023 $$ 으로 마지막 부분집합 {0,1,2,3,4,5,6,7,8,9}가 1022번째 원소이다. (0부터 시작하므로 1022번째)
따라서, 1023번째 이상 감소하는 수는 없으므로 그런 경우에는 문제의 조건대로 -1을 리턴하도록 설정한다.

코드

n = int(input())

def solve(num):
    # ex) num : 10
    # '1','0'
    # '0'
    ans.append(num)
    lastNum = int(str(num)[-1])

    # decremental number
    for i in range(lastNum):
        numStr = str(num) + str(i)
        solve(int(numStr))

if n > 1023:
    print(-1)
else:
    ans = []
    for i in range(10):
        solve(i)
    print(sorted(ans)[n])