[BOJ] 1038. 감소하는 수(Python) / DFS

1038번: 감소하는 수

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

 

• 사용 알고리즘 : DFS
• 10보다 작은 수에 대해서는 input값 그대로 출력
• depth를 최대 10까지 해보고 도중에 cnt가 N번째 수일 때 리턴한다.
• cnt는 가능한 전체 수의 인덱스라고 생각하고 depth가 limit에 다다랐을 때 +1해주며 관리한다.
• 맨 앞에 올 수 있는 숫자는 1~9까지 숫자를 순서대로 넣어준다.
• dfs 함수 안에서 현재 숫자 temp의 마지막 수보다 작은 숫자만큼 for문으로 돌리며 가능한 숫자만 temp 뒤에 붙이면 재귀로 나아간다.
• for문의 range로 depth와 limit에 올 수 있는 가능한 수를 제어한다.

 

파이썬 코드는 다음과 같다.

---

def dfs(depth, limit, temp):
    global cnt
    if depth == limit:
        cnt += 1
        # print(temp, cnt)
        if cnt == N:
            print(temp)
            exit()
        return
    for i in range(int(temp[-1])):
        dfs(depth+1, limit, temp+str(i))

# main
N = int(input())
cnt = 9
if N < 10:
    print(N)
    exit()
else:
    for k in range(1, 11):
        for n in range(1, 10):
            dfs(0, k, str(n))
print(-1)

---

• 시간 : 128ms / 메모리 : 123328kb
• 고찰 : 어렵게 생각했지만 의외로 간단한 문제였다. DFS는 풀수록 익숙해지는 것 같다.