백준 알고리즘 - 오르막수 (11057) [Python]

 문제

 

www.acmicpc.net/problem/11057

11057번: 오르막 수

 

 

 

 

 

 문제 상황

 

- 자리수 N이 주어질 때, N자리의 오르막 수의 개수를 출력한다.

 

 

 

 

 

 해결 전략

 

- 결국 포인트는 마지막 자리수이다. 즉, N자리의 수는 N-1자리 수에 끝에 오르막을 유지할 수 있는 수를 붙이는 구조이다. 이전 값을 저장하며 관찰하므로 memoization을 활용한다.

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
cache = [[0], [1 for _ in range(10)]] + [[0 for i in range(10)] for j in range(N-1)]
for i in range(2, N+1):
    for j in range(10):
        cache[i][j] = (sum([cache[i-1][k] for k in range(j+1)]))%10007
print(sum(cache[N])%10007)

 

 

 

 

 

 해설

 

- 결국 개수를 결정하는 것은 1의자리가 무슨 수인지이다. 다음 1의 자리 수는 이전 수의 1의 자리수(현재의 10의 자리수)보다 반드시 크거나 같아야하므로 이 조건을 활용하여 cache를 쌓아나간다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

-