백준 1174 <줄어드는 수> Python

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

---

문제 자체는 DFS 를 사용해 풀면 되지만 '줄어드는 수' 자체에는 자체적인 한계가 있기 때문에 모든 줄어드는 수의 개수가 궁금해졌습니다.

나아가 K 자릿수에 해당하는 줄어드는 수의 개수를 구해보고 싶어져 DP 로 해당 문제를 풀었습니다.

 

memo[i][j] 를 자릿수가 i 이고 첫 숫자가 j 인 줄어드는 수의 개수라고 정의하겠습니다.

자릿수가 i 이고 첫 숫자가 j 라면 해당 조건에서 줄어드는 수의 경우의 수는

자릿수가 i-1 이고 첫 숫자가 j 이하인 줄어드는 수의 경우의 수와 같습니다.

 

즉 memo[i][j] = sum([memo[i-1][j_in] for j_in in range(len(memo[i-1])) if j_in < j])

라고 할 수 있습니다.

 

DP 로 특정 자릿수와 특정 첫 숫자에서의 개수를 알게 되었습니다.

그렇다면 자릿수과 첫 숫자를 순회하며 개수의 합이 처음으로 N 을 넘는 순간을 알 수 있습니다.

 

그렇다면 N 번째 줄어드는 수의 자릿수와 첫 숫자는 처음으로 N 을 넘는 순간의 줄어드는 수와 첫 숫자이므로 해당 위치에서부터 순회를 시작해 답을 알 수 있습니다.

 

비교를 위해 처음부터 단순히 숫자를 1 씩 더해가며 순회했을때와 DP 로 가이드라인을 잡아 1 씩 더해가며 순회했을때 전자는 시간을 많이 초과했지만 후자는 문제를 해결할 정도로 빠르게 끝남을 볼 수 있습니다.

---

import sys

input = sys.stdin.readline

def solution(N):

    # DP / memo[i][j] = 자릿수가 i 이고 첫 숫자가 j 인 줄어드는 수의 개수

    memo = [[0 for _ in range(11)] for _ in range(11)]

    for i in range(10):

        memo[1][i] = 1

    # 자릿수가 K 인 줄어드는 수의 개수 =

    # 자릿수가 K - 1 이고 첫 숫자가 K 번째 올 수보다 작은 모든 경우의 수

   

    # 순회

    # 자릿수

    for i in range(2, 11):

        # 맨 앞에 오는 수

        for j in range(1, 10):

            # 맨 앞에 오는 수가 자릿수 - 1 이상일때만

            if j >= i-1:

                # 점화식

                memo[i][j] = sum([memo[i-1][j_in] for j_in in range(len(memo[i-1])) if j_in < j])

   

    # 카운트 합

    cnt_sum = 0

    # 직전 카운트

    before_cnt_sum = 0

    # 자릿수

    digit = 0

    # 시작 숫자

    start_num = 0

    # memo 순회하며 자릿수 / 시작 숫자 탐색

    for i in range(1, 11):

        for j in range(10):

            # 카운트 누적

            cnt_sum += memo[i][j]

            # 카운트가 N 이상이면

            if cnt_sum >= N:

                # 자릿수 / 시작 숫자 기록

                digit = i

                start_num = j

                break

            # 직전 카운트 누적

            before_cnt_sum = cnt_sum

        # 자릿수와 시작 숫자가 정해졌으면 순회 끝

        if digit:

            break

   

    # 불가능한 N 이면

    if not digit:

        return -1

    # 자릿수와 시작 숫자부터 시작

    num = ''.join([str(i) for i in range(digit-1, -1, -1)])

    num = str(start_num) + num[1:]

    num = int(num)

    # 카운트

    cnt = before_cnt_sum + 1

    # 순회

    while cnt != N:

        # 수를 늘려가며 줄어드는 수인지 판단

        num += 1

        if all([str(num)[i] > str(num)[i+1] for i in range(digit-1)]):

            cnt += 1

    return num

# 입력

N = int(input().strip())

print(solution(N))