백준 알고리즘 1038

문제

일단 문제가 이게 뭐노.......

그러니까 N번째로 감소하는 수라는 의미가 321 950과 같은 감소하는 수들 중 몇번째 감소하는 수인지 입력을 N으로 받고 해당 숫자가 무엇인지 출력하라는 것.

그렇다면 감소하는 수들을 하나의 리스트로 우선 저장해두어야 하는데
그걸 어째 해야 하나... 다른 사람들 블로그를 많이 참고해보니 재귀를 이용해서 리스트를 많이 저장해오던데 살펴보자.

참고 블로그 : https://velog.io/@gale4739/%EB%B0%B1%EC%A4%80-1038-%EA%B0%90%EC%86%8C%ED%95%98%EB%8A%94-%EC%88%98Java

위 블로그에서 말했다시피 감소하는 수는 말 그대로 이전 자릿수보다 작은 수가 따라오니 재귀를 이용해 해당 숫자를 계속해서 생성하면 된다는 것

def get_nums(now, last):
  arr.append(now)

  for i in range(now%10):
    get_nums((now*10)+i, last+1)

위 함수를 이용하면 다음 자릿수에 계속 자기보다 작은 수를 넣어 리스트에 추가해준다.

위 함수를 이해하면 다음은 쉽다. 정렬한 후 해당 배열의 N번째 값을 출력해주면 되고 배열 크기에 벗어난 경우 -1을 출력하면 된다.

여기서 제일 중요하다고 생각되는 부분은 반복문을 now%10 까지 돌린다는 것인데 왜일까?

재귀 호출을 통해 now 값이 계속해서 커지기 때문에 최초로 주어진 숫자가 10 이상이어도 자릿수를 구해야 하므로 %10을 해서 반복문을 돌려야 하는 거다. 그리고 now%10까지 돌리면서 now보다 작은 수를 다음 자리에 붙이는 게 된다.

최종 코드

def get_nums(now, last):
  arr.append(now)

  for i in range(now%10):
    get_nums((now*10)+i, last+1)

N = int(input())
arr = []

for i in range(10):
  get_nums(i,i)

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