[백준-11057] 오르막 수

나의 코드

import sys
input = sys.stdin.readline

n=int(input())

dp=[[0]*10 for _ in range(n+1)]
dp[1]=[1,1,1,1,1,1,1,1,1,1]

for i in range(2,n+1):
    for j in range(0,10):
        dp[i][j]=sum(dp[i-1][j:])

print(sum(dp[n])%10007)

수행시간: 72ms

나의 풀이

dp[i][j]는 i자리수 중 j로 시작하는 오르막수의 개수이다. 이는 i-1번째 오르막 수 중에서 첫째자리가 j와같거나 j보다 큰 수앞에 j를 추가하는 거와 같다.

다른 사람들 코드 및 풀이

import sys
input = sys.stdin.readline

n=int(input())
dp=[[0]*(10) for _ in range(n+1)]
dp[1]=[1,1,1,1,1,1,1,1,1,1]

for i in range(2,n+1):
    for j in range(10):
        for k in range(j+1):
            dp[i][j]+=dp[i-1][k]
print(sum(dp[n])%10007)

수행시간: 88ms

다른 사람들 풀이는 dp[i][j]에 i자리 중 j값이 가장 끝에 오는 오르막 수의 개수가 들어간다. j값이 가장 끝에 올라면 i-1자리 중 가장 끝에 j보다 작거나 같은 수가 와야한다.