[BOJ, 백준] 1038 - 감소하는 수 (Python)

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

문제

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

 

입력

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

출력

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

예제 입출력

풀이

 

알고리즘 분류가 백트래킹, 브루트포스로 되어있는데 이것보다는 dp느낌나게 풀었습니다.

 

먼저 arr배열에다가 1의 자리수인 숫자들을 넣어준고. [0,1,2,3,4,5,6,7,8,9]

그 다음에는 둘째 자리수를 구하기 위해서는 

10

20 21

30 31 32

40 41 42 43

50 51 52 53 54

60 61 62 63 64 65

70 71 72 73 74 75 76

80 81 82 83 84 85 86 87

90 91 92 93 94 95 96 97 98

이런식으로 가는 것을 알 수 있습니다. 이 부분은 그냥 넣어주도록 했다.

 

또 세자리수 수가 어떻게 나아가는지 보게 되면

210

310 320 321

410 420 421 430 431 432 

510 520 521 530 531 532 540 541 542 543 

....

...

이런식으로 나가는 것을 알 수있다.

 

그러면 자기 숫자의 앞자리보다 작은 수들을 모두 다 더해주는 것이다.  <-- 약간 말이 이상한데 

 

조금 자세히 예를 들어보면 

세자리수고 앞의 자리수가 6이라면 6 + (10 20 21 30 31 32 40 41 42 43 50 51 52 53 54 ) append해주는 것입니다다.

그러면 610 620 621 630 631 632 ... 652 653 654 이렇게 되는 것입니다.

 

마찬가지로 네자리부터 십의 자리수 일 때에도 이런식으로 해주면 된다.

 

ans배열에는 extend를 해주고 arr배열에는 append를 해줘서 자리수 : arr[자리수 -1]이 감소하는 수의 자리수 전체를 나타내도록 했습니다.

 

n = int(input())
ans = []
tmp = []
for i in range(1,10):
    for j in range(0,i):
        tmp.append(str(i)+str(j))
arr=[[0,1,2,3,4,5,6,7,8,9]]
ans.extend([0,1,2,3,4,5,6,7,8,9])
arr.append(tmp)
ans.extend(tmp)
k=1
while k<8:
    tmp = [] 
    for i in range(1,10):
        x = 0
        while i>int(arr[k][x][0]):
            tmp.append(str(i)+arr[k][x])
            x+=1
    arr.append(tmp)
    ans.extend(tmp)
    k+=1
print(-1 if n > len(ans) else ans[n])

 

 

혹시 틀린부분이나 이해 안가시는 부분이 있으시면 댓글 남겨주세요