감소하는 수

문제

풀이 1 (DP?)

처음 문제를 보고 DP가 아닐까 생각을 했다.
십의 자리가 3일 때를 생각해보면 올 수 있는 일의 자리는 2, 1, 0이 된다.
마찬가지로 백의 자리가 3일 때를 생각해보면 올 수 있는 십의 자리는 2, 1, 0이 된다.
여기서 일의 자리는 생각안해도 된다. DP를 사용했기 때문이다.

일의 자리 => [[0], [1], [2], [3], [4], [5], [6], [7], [8], [9]]
십의 자리 => [[], [[1, 0]], [[2, 0], [2, 1]], [[3, 0], [3, 1], [3, 2]]] ...
백의 자리 => [[], [], [[2, 1, 0]], [[3, 1, 0], [3, 2, 0], [3, 2, 1]]] ...

점화식으로 나타내면 DP[자리 수][인덱스] => DP[자리수 - 1][0] + DP[자리수 - 1][1] ... DP[자리수][인덱스 - 1] 라고 생각했다.

def solution():
    n = int(sys.stdin.readline())

    dp = []
    cnt = 0
    flg = False
    while True:
        tmp = []
        for i in range(10):
            if not dp:
                tmp.append([[i]])
                if cnt == n:
                    flg = True
                    print(i)
                    break
                cnt += 1
            else:
                prev = dp[-1]
                t = []
                for j in range(i):
                    idx_arr = prev[j]
                    for k in idx_arr:
                        t.append([i] + k)
                        if cnt == n:
                            flg = True
                            print(''.join(map(str, ([i] + k))))
                        cnt += 1
                tmp.append(t)
        dp.append(tmp)

        if flg or cnt == 1023:
            break
    if not flg:
        print(-1)
solution()

끝나는 시점은 cnt가 1023일 때이므로 종료조건을 추가해주었다.
하지만 상당히 복잡하다는 점이 문제이다.

풀이(백트래킹)

문제 힌트에서 브루트 포스, 백트래킹이 있었다.
힌트를 보고 무릎을 탁 쳤다.

def solution():
    n = int(sys.stdin.readline())

    tmp = []

    def backtracking(num):
        if len(num) == pos:
            tmp.append(int(num))
            return

        last = int(num[-1])
        for i in range(10):
            if last > i:
                backtracking(num + str(i))
            else:
                break

    for pos in range(1, 11):
        for i in range(10):
            backtracking(str(i))

    if n >= len(tmp):
        print(-1)
    else:
        print(tmp[n])
solution()

백트래킹으로 이전 숫자last보다 더 작은 숫자i를 계속 추가하고 숫자num이 자릿수pos와 같다면 배열tmp에 추가해준다.
또한 순서도 보장되므로 인덱스에 맞게 출력해주면 된다.