[백준] 11057. 오르막 수(Python, 파이썬)

백준 온라인의 문제 풀이입니다.

📖 [백준] 11057. 오르막 수

시간 제한	메모리 제한	난이도
1초	256 MB	실버 1

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

✔️ 입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

✔️ 출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

✔️ 입력 출력 예시

입력	출력
1	10
2	55

🗒️ 내 풀이

‘10,007로 나눈 나머지를 출력한다.’는 조건에서 다이나믹 프로그래밍으로 접근했다.

결국 뒤의 숫자가 앞의 숫자보다 크거나 같으면 되므로 dp[n][k]가 n번째 자리수가 k일 때 가능한 경우의 수라고 했을 때 점화식은 아래와 같다.

• n번째 자리수가 0일 경우는 바로 앞의 숫자가 0일 경우만 가능
  • dp[n][0] = dp[n - 1][0]
• n번째 자리수가 1일 경우는 바로 앞의 숫자가 0, 1일 경우만 가능
  • dp[n][1] = dp[n - 1][1]
    $\vdots$
    
• n번째 자리수가 9일 경우는 바로 앞의 숫자가 0 ~ 9일 경우만 가능

따라서 dp[n][k] = sum(dp[n - 1][:k + 1]) 이 된다.

import sys
input = sys.stdin.readline
MOD = 10007
n = int(input())
dp = [[0] * 10 for _ in range(n + 1)]
for i in range(10):
    dp[1][i] = 1

# dp[n][0] = dp[n - 1][0]
# dp[n][1] = dp[n - 1][0] + dp[n - 1][1]
# ...
# dp[n][9] = dp[n - 1][0] + dp[n - 1][1] + ... + dp[n - 1][9]
for i in range(2, n + 1):
    for k in range(10):
        dp[i][k] = sum(dp[i - 1][:k + 1]) % MOD

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