[백준] 11057번:오르막 수 (python 파이썬)

문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

 

풀이 및 소스코드

난 당연히 맨 앞에 오는 숫자부터 고려를 해주면서 규칙을 찾아보았다.

앞에서부터 하니 규칙은 보이나 규칙을 dp로 정의하기가 어려웠다.

자릿수가 주어졌을 때 맨 뒤에 오는 숫자에 대해 표를 만들어 구해보면 규칙을 쉽게 알 수 있었다.

위와 같이 num[i] += num[i-1] 이라는 규칙이 보인다.

따라서 끝까지 적용해주면 된다.

n = int(input())

num = [1]*10

for i in range(n-1):
    for j in range(1, 10):
        num[j] += num[j-1]

print(sum(num)%10007)