백준 11057번 - 오르막수

n = int(input())
def solve(n):
    arr = [[1 for _ in range(10)] for _ in range(n)]
    for z in range(1,n):
        for i in range(10):
            if i == 0: arr[z][i] = sum(arr[z-1])
            else:  arr[z][i] = sum(arr[z-1][i:])
    return(sum(arr[n-1])%10007)

print(solve(n))

어떻게 풀어야할지 감이 안잡힐때, 노트에 수도코드를 쓰면서 차분하게 정리하니 머릿속에서 깔끔하게 이해가 된다.

다이나믹 프로그래밍의 핵심은 이전에 사용했던 결과를 다시 사용하여 알고리즘 효율을 높이는 것.

 

로그인