[골드 5] 백준 1038 - 감소하는 수 (파이썬)

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

풀이

감소하는 수란 각 자릿수가 왼쪽부터 오른쪽으로 감소하는 수이다.

예를 들어서, 321, 740, 1 , 20 이런식을 의미한다.

0부터 9876543210 까지 총 1023개의 감소하는 수가 존재한 다는것을 알 수 있다.

입력 N이 주어졌을때, N번째 감소하는 수를 출력하는 문제이다.

• 만약 존재하지 않으면 -1을 출력해야 한다.

for i in range(1, 11):
    for combination in combinations(list(range(10)), i):

combinations(range(10), i)는 0~9중 i개를 뽑는 조합을 구한다

예를 들어서 i 가 2라면 (0, 1), (0, 2), … , (8, 9)와 같은 모든 조합이 나온다.

이 조합들을 역순으로 정렬하여 자릿수가 감소하는 숫자들은 만드는 문제이다.

A.sort()
if len(A) <= N:
    print(-1)
else:
    print(A[N])

생성된 감소하는 수들을 오름차순 정렬하고, N번째 인덱스에 해당하는 값을 출력한다.

N이 감소하는 수 개수보다 크면 -1을 출력하는 문제이다.

코드

# 백준 1038 - 감소하는 수
# 분류 : 브루트 포스

from itertools import combinations

N = int(input())

A = []
for i in range(1, 11) :
    for combination in combinations(list(range(10)), i) :
        gamso = 0
        for n in combination[::-1] :
            gamso *= 10
            gamso += n
        
        A.append(gamso)

A.sort()
if len(A) <= N :
    print(-1)
else :
    print(A[N])