https://www.acmicpc.net/problem/11057
시간 1초, 메모리 256MB
input :
- N (1 <= N <= 1,000)
output :
- 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력.
조건 :
- 오르막 수 = 수의 자리가 오름차순을 이루는 수.
- 인접합 수가 같아도 오름차순으로 친다.
- 수는 0으로 시작할 수 있다.
10844 번 문제와 비슷하게.
이번엔 0도 포함 할 수 있으니 빼주거나 할 필요 없다.
포인트.
숫자의 끝 자리가 0이면 그 다음 올 수 있는 숫자는 10가지 .
반복문으로 모든 dp에 들어갈 때 마다 + 1 해주고.
숫자의 끝이 1이면 그 다음 9가지....
2이면 8가지....
...
9이면 1가지....
로 반복해서 계속 채워주면 될 거 같다.
import sys
T = int(sys.stdin.readline())
dp = [[0] * 10 for _ in range(1001)]
for i in range(10):
dp[1][i] = 1
for x in range(1, 1000):
for y in range(10):
for k in range(y, 10):
dp[x + 1][k] += 1 * dp[x][y]
res = 0
for i in range(10):
res += dp[T][i]
print(res % 10007)행을 찾아 들어가서. 열의 값을 읽어서
열의 값 만큼 반복을 해야 하기 때문에 반복문을 3번 돌아야 하고.
결과가 1000번 째 까지 만들어지기 때문에 999번째 행까지만 반복이 이뤄지면 된다.
