백준 11057 오르막 수 Python

문제풀이

1. $k_t$를 길이가 t이고 k로 끝나는 오르막 수라고 하고 점화식을 세우면 다음과 같습니다.

$k_t = \sum_{l=0}^k l_{t-1}$

즉, 길이가 2인 1로 끝나는 오르막 수의 개수는 길이가 1인 0으로 끝나는 오르막 수의 합(한개(0))과 길이가 1인 1로 끝나는 오르막 수의 합(한개(1))인 2개입니다. 0 뒤에 1을 붙이고, 1 뒤에 1을 붙여 {00, 01} 두 개가 됩니다.

2. 위의 $k$를 1부터 $n$까지 올리며 계산한 후, $\sum_{k=0}^9 k_n$을 반환합니다.

Python Code

n = int(input())
li = [1] * 10
for _ in range(n-1):
    tmp = [sum(li[:i+1])%10007 for i in range(10)]
    li = tmp.copy()
print(sum(li)%10007)

Line 4, 6 : 문제의 조건에 따라 %10007을 해줍니다.

문제링크

11057번: 오르막 수