BOJ 2688 - 줄어들지 않아

문제

백준 온라인 저지 - 2688번

풀이 과정

줄어들지 않는 n 자리 수를 구하는 문제입니다.

dp(num, digit) = num 보다 크거나 같은 수로 시작하는 digit 자리 수의 개수 라고 정의한다면
다음과 같은 점화식을 도출할 수 있습니다.

dp(num, digit) = dp(num, digit - 1) + dp(num + 1, digit - 1) ...

이때 `num` 은 `0 <= num <= 9` 이어야 하며 `n 자리수` 의 줄어들지 않는 수는 `dp(0~9, n)` 입니다.

코드

T = int(input())
testcases = [int(input()) for _ in range(T)]


def solution():
    memo = [[-1] * 65 for _ in range(10)]

    for digit in range(1, 65):
        for num in range(10):
            memo[num][digit] = 0
            if digit > 1:
                for to in range(num, 10):
                    memo[num][digit] += memo[to][digit - 1]
            else:
                memo[num][digit] = 1

    for n in testcases:
        answer = 0
        for num in range(10):
            answer += memo[num][n]
        print(answer)


solution()