백준 2992 크면서 작은 수

과정

• 백트래킹 사용
• 입력 받은 수를 큰 수부터 정렬하고
• 각 자리 수를 한 번씩 사용해서
• 입력 받은 수보다 큰 경우의 숫자를 저장
• 큰 수부터 정렬했기 때문에 가장 마지막에 나온 수는 입력 받은 수보다 큰 수 중 가장 작은 수다.

inp = int(input())
N = len(str(inp))
inp_lst = list(str(inp))
inp_lst.sort(reverse=True)

visited = [False] * N
ans = 0

def main(level, now, visited):
    if level == N and int(now) > inp:
        global ans
        ans = now
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            now += inp_lst[i]
            main(level + 1, now, visited)

            visited[i] = False
            now = now[:-1]


main(0, "", visited)
print(ans)

• 백트래킹은 DFS의 한 종류이며, 재귀 문제에 들어간다는 것을 알게 됐다!
• N과 M 문제들로 모르는 새에 백트래킹 단련이 되어있었다...!