1038: 감소하는 수

풀이 시간

• 50m
• 조합으로 푸는 아이디어를 참고해서 구현했다 (골드 5치고 너무 발상이 필요한 문제같다 ㅇㅅㅇ)

구현 방식

• outer for문: 자릿수만큼 for문을 돎 (1은 한자리수, 2는 두자리수, 3은 세지리수..)

• inner for문: combination을 이용하여 i자리수를 만드는 모든 경우를 추출하여 감소하는 수를 구함
  -> 예를 들어 감소하는 두자리수를 구한다고 치면, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]에서 2개를 선택하는 조합을 먼저 구함
  -> 그 중 하나가 [0, 1]이라면 이를 내림차순으로 정렬한 후 숫자들을 붙여주면 됨

• 최종적으로 answer 리스트를 오름차순으로 정렬하면 index당 감소하는 수를 저장하고 있는 리스트가 완성된다

코드

import sys

def combination(arr, n):
    result = []
    if n > len(arr):
        return result
    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for j in combination(arr[i+1:], n-1):
                result.append([arr[i]] + j)
    return result


N = int(sys.stdin.readline().rstrip())
number = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

answer = []
for i in range(1, 11):
    for comb in combination(number, i):
        comb.sort(reverse=True)
        comb = list(map(str, comb))
        answer.append(int(''.join(comb)))

answer.sort()
if N >= len(answer):
    print(-1)
else:
    print(answer[N])

결과