백준 11057번: 오르막수 python, 파이썬

1. 문제

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

11057번: 오르막 수

 

 

 

2. 풀이

계단수 랑 굉장히 비슷한 문제인데 이번에는 증가하는 방향밖에 없으므로 9만 처리하면 된다. 가장 마지막에 9가 나온 경우 이 이 후로는 9만 나오기 때문에 한 가지 경우밖에 없다. 또 나머지 숫자는 자기 이상의 숫자이기만 하면 되므로 j와 k로 이후에 나올 수 전체를 탐색해줘야한다.

 

 

3. 구현

import sys
# sys.stdin=open('input.txt')
from collections import deque
mod = 10**4+7

N=int(sys.stdin.readline())
mm=[[1]*(10) for _ in range(N+2)]

for i in range(2,N+1): # i: 길이, j: 숫자
    mm[i][9]=mm[i-1][9]
    for j in range(0,9):
        for k in range(0,j+1):
            mm[i][j] += mm[i-1][j-k]

print(sum(mm[N])%mod)