[맛있는물회] [파이썬] <백준 알고리즘> 1038번 "감소하는 수"

문제 조건

---

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다.

 

Input

---

첫째 줄에 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

Output

---

첫째 줄에 N번째 감소하는 수를 출력한다.

 

생각한 아이디어

---

만만한 DP로 봤는데 생각보다 구현하는데 시간이 많이 걸린 문제??

 

음,, 나는 일단 DP로 규칙을  찾았다

1자리수 : 1,2,3,4,5,,,9

2자리수 : 10,[20,21], [30,31,32],,,[90,91,92,93,,,98]

3자리수 : [210], [310,320,321],,,,,

이렇게 나오는 값의 개수를 가지고 이차원 DP를 만들었다.

 

'젤 큰 자리수 값'을 col로

'자리수'를 row로 잡으면

1 1 1 1 1 1 1 1 1

1 2 3 4 5 6 7 8 9

0 1 3 6 10 15 21 28 36 45

....

....

0 0 0 0 0 0 0 0 1

마지막값은 9876543210으로

row가 0부터 9까지로 끝이난다.

 

점화식은

dp[row][col] = dp[row][col-1]+dp[row-1][col-1]

이렇게 나온다.

 

이 방식으로 끝까지 2차원 dp를 생성하면 크게 시간이 많이 소요되지 않는다.

이제 나온 값으로 값을 찾아들어가는데 이부분에서 조금 어려웠다.

 

재귀함수로 들어갔다.

 

예를 들어 250번째 감소하는 수는 8420이다.

그럼 재귀함수에 

자리수 : 4 (즉, row값인 3)

젤 첫번째 수 : 8(즉, col 값인 7)

cnt 수 : 6 (즉 4자리수이고 젤 첫번째 수가 8인 값들 중에 6번째 수라는 의미)

-> 8210 8310 8320 8321 8410 8420

이렇게 6번째 수라는 것이다.

즉, 8*** 을 찾는 것이다.

 

다음 재귀에서는 4**을 찾는다.

 

이제 2자리만 남았을 때는 넘겨받은 cnt값-1 을 return해준다.

 

음,, 좀 복잡하게 짠 것 같지만 구현해서 다행!!

 

다른분들도 재귀 및 메모이제이션 기법을 사용해서 간단하게 구현하더라.

재귀가 젤 어려워

 

소스코드

import sys
from collections import deque
from heapq import heappop,heappush
import copy
input=sys.stdin.readline

res=""

def find_big(dp,row,order):
   tmp=0
   for i in range(0,9):
      tmp += dp[row][i]
      if tmp>=order:
         return i,order-(tmp-dp[row][i])

def check(dp,num,first,second): #dp,자리수,젤큰자리의 수, 몇번째인지
   global res
   if num==1:
      res+=str(first+1)+str(second-1)
      return
   else:
      res+=str(first+1)
      first,second=find_big(dp,num-1,second)
      check(dp,num-1,first,second)

if __name__ == "__main__":
   n=int(input())
   if 10>=n:print(n)
   elif n>1022:
      print(-1)
   else:
      dp=[[0 for _ in range(10)] for _ in range(10)]
      for i in range(1,10):
         dp[0][i-1]=1
      dp[1][0]=1
      row=10
      cnt=10
      flag=0
      dp[0][9],dp[1][9]=9,1
      while flag!=1:
         SUM=0
         for col in range(1,10):
            if col==9: dp[row][col]+=SUM
            else:
               dp[row][col] = dp[row][col-1]+dp[row-1][col-1]
               SUM+=dp[row][col]
               cnt+=dp[row][col]
            if cnt>=n:
               cnt2=n-(cnt-dp[row][col])
               flag=1
               break
         row+=1

      #row + 1 자리수, col+1 젤 첫번째 수, cnt2번째 수
      check(dp,row-1,col,cnt2)

      print(res)

 

*파이썬 문법 정리