https://www.acmicpc.net/problem/11057
11057번: 오르막 수
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수
www.acmicpc.net
풀이 과정
d[i][k]를 k로 끝나는 i자리 오르막 수의 개수라고 하자.
d[i][k] = sum(d[N-1][j]) (0 <= j <= k) 가 성립한다.
소스 코드
import sys
mod = 10007
d = [[0 for _ in range(0, 10)] for __ in range(0, 1001)]
d[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
N = int(sys.stdin.readline())
for i in range(2, N+1):
for j in range(0, 10):
for k in range(0, j+1):
d[i][j] += d[i-1][k]
d[i][j] %= mod
print(sum(d[N]) % mod)'알고리즘 문제 풀이 > 백준' 카테고리의 다른 글
| 백준 1932 - 정수 삼각형 [파이썬] (0) | 2022.04.30 |
|---|---|
| 백준 2156 - 포도주 시식 [파이썬] (0) | 2022.04.30 |
| 백준 1309 - 동물원 [파이썬] (0) | 2022.04.22 |
| 백준 1149 - RGB 거리 (0) | 2022.04.22 |
| 백준 15988 - 1, 2, 3 더하기 3 [파이썬] (0) | 2022.04.21 |