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

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

import math

def search_first_num(cnt, n):
    """N번째 감소하는 수의 추가할 숫자와 자릿수를 찾는 함수"""
    while True:
        for i in range(n, 10):  # n 이상의 숫자에서 선택 (불필요한 반복 제거)
            cnt += math.comb(i, n)  # 조합 개수를 누적
            if cnt > N:  # 목표 숫자 초과 시 종료
                cnt -= math.comb(i, n)  # 초과된 값 되돌리기
                return i, n, cnt  # 현재 숫자, 자리수, 누적 개수 반환
        n += 1  # 자리수를 증가하여 다시 탐색

# 🔹 0~9까지 감소하는 수 개수(조합 개수) 미리 계산
limit = sum(math.comb(i, n) for n in range(0, 10) for i in range(n, 10))

# 🔹 입력값 받기
N = int(input())

# 🔹 가능한 감소하는 수 개수를 초과하면 -1 출력
if N > limit - 1:
    print(-1)
else:
    ans = []  # 감소하는 수의 각 자리수를 저장할 리스트
    cnt = 0  # 현재까지의 감소하는 수 개수
    n = 1  # 자리수 (1자리부터 시작)

    while True:
        i, n, cnt = search_first_num(cnt, n - 1)  # 추가할 숫자 탐색
        ans.append(i)  # 숫자 추가
        if n == 0:  # 자리수를 다 찾았으면 종료
            break

    # 🔹 리스트의 숫자들을 문자열로 변환하여 출력
    print(''.join(map(str, ans)))

감소하는수의 최대값이 있다는것을 유념하면 쉽게 조합으로 풀 수 있다.