백준 11057번 파이썬 문제풀이(DP - 오름막 수)

---

이 문제는

• 10844번 - 쉬운 계단 수

10844번: 쉬운 계단 수

의 문제와 굉장히 유사하다. 

 

dp[ N 자리의 수 ][ N 자리 숫자에서 맨 앞에 오는 수 ]

라고 생각해보자.

 

dp[1][0] ~ dp[1][9] = 1 이다.

 

N이 2부터는 다음과 같은 식이 성립한다.

dp[2][0] = dp[1][0] + dp[1][1] ... dp[1][9] 이다.

dp[2][1] = dp[1][1] + dp[1][2] ... dp[1][9] 이다.

dp[2][2] = dp[1][2] + ... dp[1][9] 이다.

 

즉 앞자리에 0이 올때는 뒷자리에 0~9이 모두 올 수 있기 때문에 0~9가 오는경우의 수를 모두 더해주면되고 1이 올때는 뒷자리에서 1~9 오는 경우의 수를 모두 더해주면 된다. 이를 점화식으로 표현하면 다음과 같은 식이 나온다.

 

import sys

input = sys.stdin.readline
N = int(input())

dp = [[1 for _ in range(10)] for _ in range(N + 1)]

for i in range(2, N + 1):
    for j in range(10):
        dp[i][j] = sum(dp[i-1][j:])

print(sum(dp[N]) % 10007)