https://www.acmicpc.net/problem/11057

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

n = int(input().strip())

# dp[i][j] = 수의 길이가 j일 때, 마지막 숫자가 i(0<=i<10)인 오르막 숫자의 개수
dp = [[0] * (n+1) for _ in range(10)]

for j in range(1, n+1):
    for i in range(10):
        # base case
        if j == 1:
            dp[i][1] = 1

        else:
            for x in range(0, i+1):
                dp[i][j] += dp[x][j-1]

# n열의 합을 출력한다
result = 0
for row in dp:
    result += row[n]
print(result % 10007)

---

🧂아이디어

(예시)

• d[4][3] = 수의 길이가 3일 때, 마지막 숫자가 4인 오르막수의 개수
• 3번째 숫자가 4가 되려면, 2번째 숫자가 0, 1, 2, 3, 4인 수들 뒤에 붙어야 하므로
• 3번째 숫자가 4인 오르막수의 개수는 d[0][2] + d[1][2] + d[2][2] + d[3][2] + d[4][2]
• 어차피 최대값이 1000이라 2차원 리스트 만드는 데 무리가 없으므로 이러한 방식으로 풀이했다.