[BOJ] Python 백준 1038번 감소하는 수 골드 5

https://www.acmicpc.net/problem/1038

1038번: 감소하는 수

문제 풀이

---

전형적으로 백트래킹을 이용하면 풀 수 있는 문제다.

지문에서 N번째 숫자를 묻고 N은 1,000,000(백만) 이하의 자연수 혹은 0이므로 상당히 큰 숫자들을 비교해야 할 것 같지만 정작 주의해야 할 조건은 딱 하나다.

 

1. 앞 자릿수부터 뒤로 갈수록 숫자가 작아져야 한다.

예시에 나온 322처럼 같은 숫자가 연속해서 등장해도 감소하는 수가 아니므로 생각 가능한 최대 숫자는 9876543210이다.

물론 이 숫자 또한 90억이 넘는 숫자이므로 0부터 9876543210까지 차례대로(선형적으로) 감소하는 숫자인지 판단하려면 엄청난 연산 횟수가 나올 수밖에 없다.

하지만 이 숫자들을 자릿수를 기준으로 비교한다면 얘기가 달라진다.

즉, 1자리 수부터 10자리 수까지 앞자리보다 작은 숫자들만 이어 붙여준다면 불필요한 연산을 획기적으로 줄일 수 있다.

이 과정에서 백 트래킹을 재귀로 구현하며 무한 루프에 빠지지 않도록 탈출 조건을 잊지 않도록 한다.

아이디어만 떠올린다면 구현 자체는 어렵지 않은 문제이므로 전체 코드를 보면서 설명하겠다.

 

def add_digit(digit,num):    #자리수에 따라 증가
    if digit==1:
        decreasing.append(num)
    else:
        for i in range(num%10):
            add_digit(digit-1,num*10+i)

def backtracking(digit):    #백트래킹 시작
    for i in range(digit-1,10):
        add_digit(digit,i)
    
decreasing=[]        #감소하는 숫자 리스트
for i in range(1,11):
    backtracking(i)

n=int(input())
if n>=len(decreasing):        #감소하는 숫자가 없을 때
    print(-1)
else:
    print(decreasing[n])

크게 구성을 함수 두 개, 메인으로 나누었다.

 

물론 메인에서 중첩 for문을 통해 1자리 수부터 10자리 수까지 가능한 숫자들을 매개변수로 보낸다면 하나의 함수만 써도 되지만 직관적인 이해를 돕기 위해 기능을 분리하여 함수 두 개로 구현하였다.

첫 번째 함수 add_digit은 특정 자릿수까지 감소하는 숫자를 이어 붙이는 함수고 두 번째 함수 backtracking은 1 자릿수부터 10 자릿수까지 백 트래킹을 반복하는 함수다.

함수의 특성상 먼저 선언되어있어야 호출 가능하므로 조금 복잡하지만 함수의 흐름대로 설명하겠다.

먼저 12번째 줄에 decreasing으로 감소하는 숫자들을 넣을 리스트를 선언했다.

그리고 13번째 줄은 자릿수를 매개변수로 백 트래킹을 시작하기 위한 반복문이고 이해가 쉽도록 1부터 10까지 반복한다.

즉 1 자릿수부터 10자리 수까지 찾겠다는 의미이다.

그럼 8번째 줄인 backtracking 함수로 넘어가는데 이미 받은 digit변수와 같이 0부터 9까지 숫자를 파라미터로 넘긴다.

이 0부터 9는 실제 감소하는 수가 될 숫자들이다.

그렇게 add_digit으로 넘어가면 digit이 1자리일 때는 더 이상 추가할 숫자가 없으므로 decreasing 리스트에 숫자를 넣고 함수가 자동 종료된다.

만약 digit이 2 이상일 땐 뒷자리에 숫자를 추가해야 하므로 반복문을 통해 digit을 감소시킨 후 재귀 호출한다.

이때 추가해야 할 숫자가 바로 앞자리 숫자보다 작아야 하므로 num%10을 통해 바로 앞자리 숫자를 구하고 해당 숫자 미만까지만 반복문을 돌린다.

물론 2자리 수 이상부터는 첫자리에 0이 올 수 없지만 num%10은 0이라 for문을 수행하지 않아서 고려하지 않아도 된다.

또한 뒷자리에 숫자를 이어 붙이므로 원래 숫자인 num에 10을 곱해서 자릿수를 늘린 후 i를 더하면 원하는 숫자가 된다.

위의 재귀가 끝나면 decreasing 리스트에는 0부터 9876543210까지 감소하는 수가 들어가게 되고 N을 입력받아서 리스트의 인덱스를 벗어나면 불가능한 수이므로 -1을 출력, 벗어나지 않으면 해당 인덱스의 숫자를 출력하면 통과한다.

 

결과 화면

아무래도 이 문제가 골드로 측정된 것은 숫자를 자릿수로 비교하는 생각의 전환, 백 트래킹 적용 때문인 것 같다.

비교적 코드도 짧고 구현도 쉬운 편이기 때문이다.

아마 다양한 문제를 접하다 보면 이 정도 아이디어와 구현은 쉽게 떠올리고 구현할 수 있을 것이다.