오르막 수 (BOJ-11057)
in ALGORITHM
‘시간제한 1초, 메모리제한 256MB, BOJ-11057’
오르막 수 (BOJ-11057)
이 문제는 이전에 쉬운 계단수 문제와 비슷하다. 과정에서 점화식을 찾을 수 있다.
n이 증가 할 때마다 각 숫자들이 마지막 자릿수에 오는 경우의 수를 보면 규칙이 보인다.
우선 한자리의 경우 모두 경우의 수가 1이 되는걸 알 수 있다.
그리고 두자리의 경우 마지막 자리가 0일 경우는 1가지이다. 앞이 0인 경우 한 가지 뿐이기 때문이다. (00)
마지막 자리가1인 경우는 앞이 1보다 작거나 같아야 하므로 2가지이다.
이런식으로 계속 경우의 수를 구해보면 다음과 같다.
여기서 규칙을 찾아보면 이전 자릿수에서의 0부터 현재숫자까지의 경우의 수를 합친 값이 현재 자릿수의 현재 숫자의 경우의 수인걸 알 수 있다.
dp[i][j] = dp[i-1][0] + ... + dp[i-1][j]
이런 식으로 dp를 구하고 해당 자릿수의 dp의 경우의 수들을 모두 합쳐주면 원하는 답이 나오게 된다.
n = int(input())
dp = [[0] * 10 for _ in range(1001)]
for i in range(10):
dp[1][i] = 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)
