백준 1038번

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

1038번: 감소하는 수

N = int(input())

arr = []

cnt= 0 
number = 0 

# 수 찾기
def find_down(length, n):
  global arr

  #숫자길이가 같을 때 배열에 추가
  if len(n)==length:
    arr.append(int(n))
    return True

  #현재 숫자길이가 0일때
  if len(n)==0:
    # 맨 앞의 수가 감소하는 수가 될 수 있도록 설정
    for i in range(length-1,10):
      find_down(length,n+str(i))
  
  else:
    #감소하는 수가 될수 없는 경우
    if n[-1]==0: 
      return False
    #0부터 앞의 수보다 작은 수까지만 가능
    for i in range(int(n[-1])):
      find_down(length,n+str(i))

#N==0일때 예외처리
if N==0:
  print(0)


else:
  #감소하는 수가 가능한것은 1~9876543210
  for i in range(1,11):
    find_down(i,'')

  try:
    print(arr[N])
  #오류시 -1출력
  except:
    print(-1)

 

감소하는 수가 되는 경우는 1~9876543210

하지만 이를 전부 하나하나 찾으면 시간 초과 발생

 

따라서 수 찾기 함수를 사용하여 1부터 10자리 감소하는 수를 찾아줌

문자열을 이용해, 맨 뒤에 위치하는 수보다 작은 수를 추가 해주고

조건에 만족하지 않으면 False

 

배열의 길이가 원하는 자릿수만큼 커지면 감소하는 수 추가

# 수 찾기
def find_down(length, n):
  global arr

  #숫자길이가 같을 때 배열에 추가
  if len(n)==length:
    arr.append(int(n))
    return True

  #현재 숫자길이가 0일때
  if len(n)==0:
    # 맨 앞의 수가 감소하는 수가 될 수 있도록 설정
    for i in range(length-1,10):
      find_down(length,n+str(i))
  
  else:
    #감소하는 수가 될수 없는 경우
    if n[-1]==0: 
      return False
    #0부터 앞의 수보다 작은 수까지만 가능
    for i in range(int(n[-1])):
      find_down(length,n+str(i))