[Python] 백준 1174 줄어드는 숫자

1. 문제 링크

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

1174번: 줄어드는 숫자

---

2. 문제 요약

n번째로 줄어드는 수 구하기

---

3. 아이디어 정리

• 백트래킹 이용
  • 마지막 값 > 현재 값 경우, 재귀 진행하여 감소하는 수를 만들어 준다.
  • 감소하는 수를 정렬한다.
• 조합 이용
  • 0~9로 하나씩 조합 만들기
  • 모든 조합을 정렬한다.

---

4. 문제 풀이

4-1. 백트래킹 이용

import sys
arr = list()
result = set()
def dfs():
    if len(arr) > 0:
        result.add(int("".join(map(str, arr))))

    for i in range(0, 10):
        if len(arr) == 0 or arr[-1] > i:  # 마지막 값이 더 큰 경우
            arr.append(i)
            dfs()
            arr.pop()

n = int(sys.stdin.readline())

try:
    dfs()
    result = list(result)
    result.sort()
    print(result[n - 1])
except:
    print(-1)

4-2. 조합 이용

import sys
from itertools import combinations

n = int(sys.stdin.readline())

nums = list()               # 모든 감소하는 수
for i in range(1, 11):      #  1~10개의 조합 만들기 (0~9개니깐)
    for comb in combinations(range(0, 10), i):  # 0~9로 하나씩 조합 만들기
        comb = list(comb)
        comb.sort(reverse=True)                     # 해당 조합을 감소하는 수로 변경
        nums.append(int("".join(map(str, comb))))

nums.sort()   # 오름차순

try:
    print(nums[n - 1])
except:     # 인덱스가 넘어가는 경우 -1 출력. 마지막 수 9876543210
    print(-1)

 

---

5. 결론

• 백트래킹이나 조합을 이용한다.
• 비슷한 문제 : https://www.acmicpc.net/problem/1038

1038번: 감소하는 수