[파이썬] 백준 11057 : 오르막 수 (실버1)

[파이썬] 백준 11057 : 오르막 수 (실버1)

 

11057번: 오르막 수

---

문제

---

풀이

방향성 생각

2차원 dp 배열을 만들준다.

0부터 시작할 수 있으니 모든 시작점을 1로 초기화한다.

마지막 숫자가 n보다 같거나 큰 숫자들은 모두 등장할 수 있다.

0보다 같거나 작은 수라 생각해도 무방하다 (대칭형)

dp[자리수][선택한 숫자] = sum(dp[이전 자리수][0부터 선택한 숫자까지])%k

 

전체 코드

n = int(input())
dp = [[0]*10 for i in range(n)]
dp[0] = [1]*10
k = 10007
for dist in range(n-1):
    for i in range(10):
        dp[dist+1][i] = sum(dp[dist][0:i+1])%k
print(sum(dp[-1])%k)