알고리즘/문제풀이

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

정찡이 2021. 10. 8. 16:44
728x90

1. 문제 링크

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

 

1174번: 줄어드는 숫자

음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어

www.acmicpc.net

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. 결론

 

1038번: 감소하는 수

음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를

www.acmicpc.net