문제
접근
DP 문제이다.
오르막수가 되기 위해선 자신 앞자리의 숫자보다 크거나 같아야한다.
이를 통해 DP를 구상하면 된다.
나는 DP를 자릿수와 각 자리마다 0~9까지로 하여 10개로 구성했다.
DP(i, j) = i번째 자리에 j가 들어왔을 때 가능한 경우의 수이다.
DP(2, 3) = 2번째 자리가 3일 때 오르막 수인 경우의 수이다.
DP(i, j) = DP(i, j-1) + DP(i-1, j) 이다.
즉, 현재 자리수에서 j-1인 경우 + 앞 자리에 j가 나온 경우이며,
n자리에서 오르막 수인 경우의 수는 sum(DP(n))으로 구할 수도 있고,
DP(n+1, 9) = sum(DP(n))을 항상 만족한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
n = int(input())
dp = [[1] * 10 for _ in range(n+2)]
for i in range(2, n+2):
for j in range(1, 10):
dp[i][j] = (dp[i][j-1] + dp[i-1][j]) % 10007
print(dp[n+1][9])