[BOJ] 11057번 - 오르막 수

---

문제설명

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

11057번: 오르막 수

사고과정

• 이 문제도 DP 테이블을 2차원 리스트로 정의해야 한다. 이 때, 행($i$)는 N을, 열($j$)는 가장 앞에 오는 숫자 0~9를 의미한다. 결국 DP 테이블에 들어가는 값은 앞에오는 숫자가 0~9 중 하나일 때, 만들 수 있는 오르막 수 개수를 의미한다.
• N = 1일 때는 즉, 0~9까지 모두 1개밖에 존재하지 않는다. N = 2일 때는 앞에오는 숫자가 0일 때는 뒤에 0부터 9까지 총 10개가 들어갈 수 있다(00, 01, 02, ..., 09) 이 떄, 00도 세주어야 하는 이유는 문제에서 숫자는 인접한 수가 같아도 오름차순으로 친다고 했으며 0으로 시작할 수 있다고 했기 때문이다.
• N = 2까지 적어보면 규칙을 발견할 수 있다. 즉, 앞에오는 숫자 0부터 9 중 하나에 따라 바로 DP 테이블의 위 행의 해당 열부터 모든 값을 더해준 값이랑 동일하다. 말로 설명하니 이해가 안될 듯 하다. 그래서 점화식을 세우면 다음과 같다. $dp[i][j] = sum(dp[i-1][j:]$
• 참고로 주어진 데이터 최대 범위가 1,000이기 때문에 2차원 리스트를 운용해도 메모리 초과를 하지 않으며 약 만 번의 연산 시간 복잡도가 소요되므로 1초 시간 내에 통과될 수 있다.

풀이

import sys

input = sys.stdin.readline
n = int(input())
mod = int(1e4) + 7
dp = [[0] * 10 for _ in range(n+1)]
for j in range(10):
    dp[1][j] = 1

for i in range(2, n+1):
    for j in range(0, 10):
        dp[i][j] = sum(dp[i-1][j:])

print(sum(dp[n]) % mod)