[백준] 1038 감소하는 수 파이썬

문제

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

입력

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

출력

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

 

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

1038번: 감소하는 수

 

---

풀이

문제 이해부터 시간이 좀 걸렸다.

한 자리 수나 같은 숫자가 연속된 수도 '감소하는 수'에 해당하는지 헷갈려서 하나하나 예제의 입출력과 대조해봤다.

한 자리 수는 포함이고, 같은 숫자가 연속된 수는 미포함이다.

 

이 문제는 동적계획과 완전탐색 그 어딘가인 것 같다..

 

감소하는 수의 규칙을 알아보았다.

먼저 한 자리 수에서 감소하는 수의 개수는 다음과 같다.

1 + 1 + 1 + 1 + 1 + 1 + 1 .. (0부터 9까지 총 10개)

 

 

두 자리 수에서 감소하는 수는 다음과 같다.

0 + 1 + 2 + 3 + 4 ....  + 9 (9x)

처음 0은 00에서 얻은 것이고 10에서 1개 20에서 20, 21로 2개 ... 이렇게 얻을 수 있다.

 

 

세 자리 수에서 감소하는 수는 다음과 같다.

0 + 0 + 1 + 3 + 6 + 10 + 15 ..... 

 

이쯤 되면 규칙이 보이는데 i번째 자리수는 i-1번째 자리수의 누적값과 같다.

다만 앞에 0이 추가되며 한 칸씩 밀린다.

 

그 규칙을 바탕으로 감소하는 수의 개수를 저장하는 배열 nums를 만들었다.

 

 

이제 몇 번째인지만 찾으면 된다.

nums를 만들면서 total에 값을 누적한다.

만약 다음 숫자를 추가했는데 total의 값이 n보다 크다면 i 자리수의 j로 시작하는 수들 중 정답이 있다는 뜻이다.

 

find_num 함수로 넘겨서 수를 찾는다.

첫 번째 숫자는 결정되었으니 dif로 i-1번째 자리수의 값을 찾는다.

하나씩 값을 누적하며 dif보다 값이 커지면 두 번째 자리수를 고정하고 i-2자리수를 찾는다.

그렇게 계속해나가면 값을 찾을 수 있다.

 

다만 한 자리 수는 따로 처리해 줘야 한다.

import sys
n = int(input())

nums = [[0]*10] + [[1]*10] + [[0]*10 for _ in range(9)]

if n <= 9:
    print(n)
    sys.exit()

n -= 1
def find_num(i, j):
    dif = n-total
    res = str(j)

    while i > 1:
        for ji in range(i-2, 10):
            dif -= nums[i-1][ji]
            if dif < 0:
                dif += nums[i-1][ji]
                res += str(ji)
                i -= 1
                break
    print(res)

total = 9
for i in range(2, 11):
    for j in range(i-1, 10):
        nums[i][j] = sum(nums[i-1][:j])
        total += nums[i][j]
        if total > n:
            total -= nums[i][j]
            print(*nums, sep="\n")
            find_num(i, j)
            sys.exit()

print(-1)

 

한 번 틀렸었는데 문제는 'n번째 수'를 구해야 하는 반면 나는 n번째 감소하는 수의 개수로 찾았기 때문에 생긴 오류였다.

0은 감소하는 수이지만 0번째 수로 쳤기 때문이다

n에 1을 빼서 해결할 수 있었다.

 

총 한시간 반 쯤 걸렸다.

 

중요한 예시를 적어놓자면

1022는 9876543210

1023은 -1이 출력되어야 한다.