🟩 [백준] [Python] [Silver1] 11057번_오르막 수

문제

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

풀이

# 백준 11057번 문제 - 오르막 수
n = int(input())
dp = [1]*10
for i in range(1,n) :
    for j in range(1,10) :
        dp[j] += dp[j-1]

print(sum(dp)%10007)

DP 문제이다. 

i 자리 수 \ j	0으로 끝나는 숫자	1	2	3	4	5
n = 1	1	1	1	1	1	1
n = 2	1	2	3	4	5	6
n = 3	1	3	6	10	15	21

 

위와 같은 표를 구할 수 있다. 이를 점화식으로 바꾸면 

dp[j] = dp[j] + dp[j-1]

이렇게 된다.