[백준 11057] 오르막 수
Tip
•
맨 앞자리 수가 0이면 다음 숫자로 0~9 가능
◦
dp[i][0] = dp[i - 1][0] + dp[i - 1][1] + ... + dp[i - 1][8] + dp[i - 1][9]
•
맨 앞자리 수가 1이면 다음 숫자로 1~9 가능
◦
dp[i][1] = dp[i - 1][1] + dp[i - 1][2] + ... + dp[i - 1][8] + dp[i - 1][9]
→ dp[i][j] += dp[i - 1][k] (k -> j to 10) 성립
풀이 소스 코드
import sys
si = sys.stdin.readline
n = int(si())
d = [[0] * 10 for _ in range(n + 1)]
# 1 자리수는 1로 초기화
for i in range(10):
d[1][i] = 1
# 보톰업 DP
for i in range(2, n + 1):
for j in range(10):
for k in range(j, 10):
d[i][j] += d[i - 1][k]
print(sum(d[n]) % 10007)
Python
