백준 알고리즘
[백준/Python]11057_오르막 수
헝그리개발자
2021. 6. 4. 14:07
문제
https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
풀이
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | sum |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 10 |
| 2 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 55 |
| 3 | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 220 |
표에서 n은 자릿수, n 옆에 숫자들은 n 자리 수의 맨 마지막 숫자, sum은 행의 합을 의미합니다.
다이나믹 프로그래밍으로 풀면 점화식을 구할 수 있는데 'dp[i][j] = dp[i-1][0]부터 dp[i-1][j]까지 합'으로 표현할 수 있습니다.
코드
import sys
n = int(sys.stdin.readline().rstrip())
dp = [[0] * 10 for _ in range(n + 1)]
for i in range(10):
dp[1][i] = 1
for i in range(2, n + 1):
for j in range(10):
for k in range(j + 1):
dp[i][j] += dp[i - 1][k]
print(sum(dp[n]) % 10007)