[백준][재귀] 감소하는 수

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

1038번: 감소하는 수

 

내가 작성한 코드

import sys

read = sys.stdin.readline

def get_count(N, r, cnt, target):
    for i in range(r):
        if N == 1:
            cnt += 1
            if target == cnt:
                return str(i), cnt

        else:
            k, cnt = get_count(N-1, i, cnt, target)
            if target == cnt:
                return str(i)+k, cnt

    return "", cnt


def get_decrease(N):
    if N < 10:
        return N

    cnt = 9
    n = "0"
    s = ""
    while cnt != N and len(n) < 10:
        for i in range(1, 10):
            s, cnt = get_count(len(n), i, cnt, N)
            s = str(i) + s
            if cnt == N:
                break
        if cnt == N:
            break
        n += "0"
    if len(n) == 10:
        return -1
    return s

N = int(read().rstrip())
print(get_decrease(N))

• 재귀
  
  • 10, 20, 30, ..., 90, 100, 200, 300, ...에 대해 재귀
  • 앞자리 수보다 작은 수마다 재귀
  • 마지막 자리수에서 cnt 증가
  • target == cnt면 탐색 중지

 

다른 사람이 작성한 코드

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])
except:     # 인덱스가 넘어가는 경우 -1 출력. 마지막 수 9876543210
    print(-1)

• 조합
  
  • 감소하는 수의 최대값은 9876543210
    - 첫 번째 for문은 1의 자리수 ~ 10의 자리수
  • 감소하는 수는 각 자리수가 동일한 값을 가질 수 없음
    - 0~9의 수에서 r개 뽑은 조합의 내림차순은 무조건 감소하는 수
  • combinations는 인덱스가 작은 값부터 선택
    - combinations로 도출되는 결과는 오름차순
• 문제를 명확하게 이해하셨기 때문에 깔끔한 알고리즘과 코드가 나왔다고 생각함

https://ryu-e.tistory.com/59

[Python] 백준 1038 감소하는 수

기억해야할 것

• 코드가 조잡함
  
  • 코드 설계를 제대로 못했을 때 코드가 항상 조잡하게 짜여지는 듯
  • 통과는 했지만, 사용되는 변수 / if-else 조건 등이 난잡함
  • 특히 숫자에 대한 재귀 문제에서 많이 어려움을 느끼는듯