[python] 백준 - 1174. 줄어드는 숫자

🤔문제 해결

못풀다가 문제 유형에 백트래킹이 있길래 힌트를 얻어 백트래킹으로 구현해봤다.

• 아이디어는 현재 숫자의 끝자리보다 낮은 숫자들을 뒤에 추가하는 재귀함수를 만들었다.
  • 현재 764이면
    • 7640 => 끝
    • 7641 => 76410 => 끝
    • 7642 => 76420 => 76421 => 764210 => 끝
• 마지막에 sort만 해주면 빠른 시간 내에 모든 경우의 수를 순서대로 다 얻을 수 있다.

 

가끔 안풀리면 다른 사람의 코드를 참고하기 전에 유형으로 힌트를 얻어보자😀

💻소스 코드

N = int(input())


# 백트래킹을 이용한 문제 풀이
def bt(cur):
    answer.append(int(cur))
    for j in range(0, int(cur[-1])):  # 현재 숫자의 끝자리보다 낮은 숫자들만 그 다음 자리수에 추가한다.
        bt(cur + str(j))


if N > 1023:  # 갯수가 1023개인듯... 0 부터 9876543210 까지 이므로 얼마 안나옴
    print(-1)
else:
    answer = []
    for i in range(10):  # 맨 앞자리가 0, 1, ,... , 9
        bt(str(i))

    print(sorted(answer)[N - 1])

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE