BOJ 11057 오르막 수

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번째 행까지만 반복이 이뤄지면 된다.