[백준] 11057번 오르막 수

💡문제접근

• 이전 포스팅에 있었던 [[백준] 10844번 쉬운 계단 수] 문제와 유사한 형태의 DP문제였다.
  이 문제를 해결할 때 역시 마지막 자릿수가 0~9인 경우의 빈도를 dp배열에 저장해서 해결하였다.

숫자의 자릿수	0	1	2	3	4	5	6	7	8	9	결과
1	1	1	1	1	1	1	1	1	1	1	10
2	1	2	3	4	5	6	7	8	9	10	55
3	1	3	6	10	15	21	28	36	45	55	220

• 누적 합 방식으로 값이 저장되는 규칙성을 확인할 수 있다.

💡코드(메모리 : 31256KB, 시간 : 80ms)

import sys
input = sys.stdin.readline

N = int(input().strip())
dp = [[0] * 10 for _ in range(1001)]

for i in range(10):
    dp[1][i] = 1
    for a in range(2, N+1):
        for b in range(10):
            dp[a][b] = sum(dp[a-1][:b+1])
print(sum(dp[N]) % 10007)

💡소요시간 : 5m