감소하는 수 [백준 1038] - python

# 조합을 이용한 코드
from itertools import combinations
import sys
input = sys.stdin.readline

def BOJ1038() :
  N = int(input())
  answers = []

  for i in range(1, 11) :
    for comb in combinations(range(0, 10), i) :
      comb = list(comb)
      comb.sort(reverse=True)
      answers.append(int("".join(map(str, comb))))

  answers.sort()
  
  try :
    print(answers[N])
  except :
    print(-1)
  
BOJ1038()
# https://ryu-e.tistory.com/59

# 재귀를 이용한 코드
import sys
input = sys.stdin.readline

def BOJ1038() :
  N = int(input())
  answers = []

  def get_decrease(num) :
    answers.append(num)

    peak = int(str(num)[0])
    for i in range(peak + 1, 10) :
      get_decrease(int(str(i) + str(num)))

  for i in range(10) :
    get_decrease(i)
    
  answers.sort()

  try :
    print(answers[N])
  except : 
    print(-1)

BOJ1038()

 

다른 분의 코드를 참고했는데 신선했다.

풀이 접근 방법: 

 

조합을 이용한 코드

1. 1자리 부터 10자리 까지 0~9 까지 숫자의 조합을 구한다.

2. 순열이 아니라 조합이므로 중복되는 숫자는 등장하지 않는다.

3. 추출된 숫자를 거꾸로 정렬한다. 이후에 정답 배열에 넣어주면 끝이다.

 

재귀를 이용한 코드

1. 0부터 9까지 탐색을 한다.

2. 재귀함수를 선언하고 재귀함수 내부에서 들어온 숫자의 맨 처음 값 (20 => 2) + 1부터 10까지 탐색한다.

3. 입력받은 숫자보다 항상 커야 하므로 str(i) + str(num) 형태로 계속 재귀를 호출해준다.

 

 

 

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

1038번: 감소하는 수

https://ryu-e.tistory.com/59

[Python] 백준 1038 감소하는 수