백준 1038 감소하는 수

정글 수료 후
새롭게 시작하는 알고리즘

나만무 기간 폭탄 맞은 잔디밭을 채워보자

1038 감소하는 수

문제

각 자리수가 강한 단조 감소하는 수를 '감소하는 수'라고 할 때
N번 째로 작은 감소하는 수를 찾는 것이 문제이다.

예:
54321 - 감소하는 수
54421 - 감소하는 수 아님
12345 - 감소하는 수 아님
0 - 감소하는 수

풀이

숫자를 0에서 부터 순회하면서 각 수가 감소하는 수인지 판단하는 것이 가장 단순한 완전탐색이다.
감소하는 수인지 판단하는 함수에 백트래킹을 적용하면 약간 더 빨라질 것이다.
또 중간에 굳이 살펴보지 않아도 되는 수가 존재한다.
예를 들어 10까지 순회했다고 했을 때, 11부터 19까지는 굳이 살펴보지 않아도 된다. 바로 20으로 가면 된다.

class Number:
    def __init__(self):
        self.number = [0,0,0,0,0,0,0,0,0,0] # 각 자리수. 0인덱스가 가장 작은 자리수이다.

    def __str__(self):
        end = self.number.index(max(self.number))
        return ''.join(map(str, reversed(self.number[:end+1])))

    def increase(self):
        for i in range(10):
            if self.number[i] == 9:
                if i >= 9:
                    raise ValueError("감소하는 수 없음")
                self.number[:i+2] = list(range(i+2))
                break
            elif self.number[i+1] == 0 or self.number[i]+1 < self.number[i+1]:
                self.number[i] += 1
                self.number[:i] = list(range(i))
                break

N = int(input())
number = Number()

try:
    for _ in range(N):
        number.increase()
    print(number)
except ValueError:
    print(-1)