99클럽 코테 스터디 27일차 TIL + 백트래킹

문제

백준 감소하는 수 https://www.acmicpc.net/problem/1038

 

코드

n = int(input())

if n > 1022:
    print(-1)
else:
    num = []
    ans = []

    def check(i):
        global num
        if len(num) == 1:
            return True
        if num[-2] > i:
            return True

    def dfs(depth):
        global num

        for i in range(10):
            num.append(i)
            if check(i):
                dfs(depth + 1)
                ans.append(int(''.join(str(x) for x in num)))
            num.pop()

    dfs(0)
    ans.sort()

    print(ans[n])

 

풀이

감소하는 수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, ... , 9876543210 순으로 나열된다.

if n > 1022:
    print(-1)

9876543210은 1022번째 숫자이므로, 1023번째부터는 감소하는 숫자가 없다.

따라서 n이 1022를 초과하면 -1을 출력한다.

 

def check(i):
    global num
    if len(num) == 1:
        return True
    if num[-2] > i:
        return True

해당 배열이 감소하는 수인지 확인하는 함수다.

한자리 수라면 True를 반환한다.

추가된 수가 바로 앞의 수(num[-2])보다 작으면 True를 반환한다.

 

def dfs(depth):
    global num

    for i in range(10):
        num.append(i)
        if check(i):
            dfs(depth + 1)
            ans.append(int(''.join(str(x) for x in num)))
        num.pop()

감소하는 수를 num배열에 담고, 이를 ans 배열에 추가한다.

그리고나서 num은 pop()으로 빈배열을 만든 뒤

다음 감소하는 수를 구해서 num 배열에 담고, ans 배열에 추가하고 다시 num을 빈배열로 만들고...

이 작업을 최대 감소하는 수 9876543210 까지 반복한다.

 

dfs(0)
ans.sort()

#출력
print(ans[n])

dfs(0)를 실행하여 위의 함수를 실행하고,

N번째 감소하는 수를 알아야하기 때문에, 감소하는 숫자들이 담긴 ans배열을 오름차순 정렬한다.

이러면 ans배열에는 0부터 9876543210 까지 감소하는 수만 담긴 오름차순 배열이 될것이다.

 

새롭게 배운점 / 느낀점

• 처음 문제 접근할때 0 ~9876543210 모두 탐색하며 감소하는 수라면 인덱스를 하나씩 늘리다가, 인덱스가 n과 같아지면 탐색한 해당 수를 반환하는 방식으로 했는데 maximum recursion depth 에러가 걸려 풀기 어려웠다.
• 때로는 숫자를 정수형을 넘어 문자형으로 바라보는 관점도 필요할것 같다.

 

더 나은 의견이나 궁금하신게 있다면 편하게 댓글 달아주세요 :)