악곱 == 악성곱슬

다이나믹 프로그래밍

---

해당 문제는 수가 오름차순을 이루는 수의 개수를 구하는 문제이다.

수의 길이가 N으로 최대 1000까지이다.

가장 먼저 떠오르는 방법은 수를 왼쪽부터 채워가며 한자리씩 재귀함수를 통해 구현하는 것이다. 아래와 같이 구현할 수 있다.

import sys

def dp(num, depth, n):
    if depth == n:
        return table[num]
    result = 0
    for i in range(num, 10):
        result += dp(i, depth + 1, n)
    return result

def solution(n):
    answer = 0
    for i in range(10):
        answer += dp(i, 1, n)
    return answer

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    sys.setrecursionlimit(100000)
    table = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    print(solution(N))

위 코드와 같이 구현하면 완전 탐색을 하며 수많은 중복 연산이 발생하여 시간초과가 발생하게 된다. 최대 10^1000 만큼 연산을 진행을 해야 하는데 말이 안된다. 따라서 중복 연산을 제거하는 DP를 떠올릴 수 있다.

따라서 DP 트리 구조도를 그려보니 level-order로 트리를 탐색하며 각 자리수에 대한 값을 DP테이블로 구현하여 서브트리의 값을 계속 업데이트 하는 방식으로 구현할 수 있다.

import sys

def solution(n):
    for i in range(n-1):
        for j in range(10):
            table[j] = sum(table[j:10]) % 10007
    return sum(table) % 10007

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    table = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    print(solution(N))