Search

[백준 11057] 오르막 수

[백준 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